<!DOCTYPE html>
<html lang="en">
  <head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta name="author" content="Zhou Wei <zromyk@163.com>">
  <title>计算机考研-算法与数据结构</title>
  <link rel="shortcut icon" href="/favicon.ico">
  <link rel="stylesheet" href="/style/pure.css">
  <link rel="stylesheet" href="/style/main.css">
  <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.css">
  <script src='/style/latest.js?config=TeX-MML-AM_CHTML'></script>
  <script src="https://cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>
  <script src='/style/Valine.min.js'></script>
  <link href="https://apps.bdimg.com/libs/highlight.js/9.1.0/styles/default.min.css" rel="stylesheet">
  <script src="https://apps.bdimg.com/libs/highlight.js/9.1.0/highlight.min.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
  <script src="https://cdn.geogebra.org/apps/deployggb.js"></script>
  <script src="https://cdn1.lncld.net/static/js/2.5.0/av-min.js"></script>
  <script src='/style/readTimes.js'></script>
</head>
<body>
  <div id="menu-background"></div>
  <div id="menu">
    <div class="pure-menu pure-menu-horizontal">
  <div id="menu-block">
    <ul class="pure-menu-list">
      <a class="pure-menu-heading" href="/index.html">ZROMYK</a>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/index.html">主页</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/archive/index.html">归档</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/download/index.html">下载</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/feedback/index.html">反馈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/about/index.html">关于我</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="https://github.com/zromyk"><i class="fa fa-github" style="font-size:32px"></i></a>
</li>

    </ul>
  </div>
</div>

  </div>
  <div id="layout">
    <div class="content">
      <div id="content-articles">
  <h1 id="计算机考研-算法与数据结构" class="content-subhead">计算机考研-算法与数据结构</h1>
  <p>
    <span>1970-01-01</span>
    <span><span class="post-category post-category-cs">CS</span></span>
    <span id="/public/article/计算机考研-算法与数据结构.html" class="leancloud_visitors" style="display:none" data-flag-title="计算机考研-算法与数据结构"></span>
  </p>
  <blockquote class="content-quote">
<p>补充学习资料：<a href="https://www.cs.usfca.edu/~galles/visualization/Algorithms.html">Data Structure Visualizations</a></p>
</blockquote>
<h2 id="_1">第一章 绪论</h2>
<h4 id="1">1、算法与数据结构基本概念</h4>
<p>数据元素：是数据的基本单位</p>
<p>数据结构包括三方面：</p>
<ol>
<li>逻辑结构</li>
<li>存储结构</li>
<li>数据的运算</li>
</ol>
<h4 id="_2">例题</h4>
<blockquote class="content-quote">
<ol>
<li>可以用【<strong>抽象数据类型</strong>】定义1个完整的数据结构。</li>
<li>以下属于<strong>逻辑结构</strong>的是？A.顺序表，B.哈希表，【<strong>C.有序表</strong>】，D.单链表</li>
<li>以下与数据的<strong>存储结构无关</strong>的术语是？A.循环队列，B.链表，C.哈希表，【<strong>D.栈</strong>】</li>
<li>以下关于数据结构的说法中，正确的是：【<strong>数据的逻辑结构独立于其存储结构</strong>】</li>
<li><strong>链式</strong>存储设计时，<strong>结点内</strong>的存储单元地址：【<strong>一定连续</strong>】</li>
</ol>
</blockquote>
<h3 id="_3">知识点</h3>
<p><strong>1.以下算法的时间复杂度为</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">void fun(int n) {
    int i = 1;
    while (i &lt;= n) {
        i = i * 2;
    }
}
</code></span></code></pre>
<p>
<script type="math/tex">2^t \le n </script>，结果为<script type="math/tex">O(\log_2n)</script>
</p>
<p><strong>2.【2011年统考真题】以下算法的时间复杂度为</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">x = 2;
while (x &lt; n/2) {
    x = x * 2;
}
</code></span></code></pre>
<p>
<script type="math/tex">2^{t+1} \lt \cfrac{n}{2} </script>，结果为<script type="math/tex">O(\log_2n)</script>
</p>
<p><strong>3.【2013年统考真题】已知两个长度分别为m和n的升序链表，若将他们合并为长度m+n的一个降序链表，在最坏的情况下的时间复杂度是【<script type="math/tex">O(max(m,n))</script>】</strong></p>
<p><strong>4.【2014年统考真题】下列程序段的时间复杂度是</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">count = 0;
for (k = 1; k &lt;= n; k *= 2) {
    for (j = 1; j &lt;= n; j++) {
        count++;
    }
}
</code></span></code></pre>
<p>
<script type="math/tex">2^k \le n</script>即<script type="math/tex">k \le \log_2n</script>
<br />
<script type="math/tex">j \le n</script>
</p>
<p>结果为<script type="math/tex">O(n\log_2n)</script>
</p>
<p><strong>5.【2017年统考真题】下列函数的时间复杂度是</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">int fun(int n) {
    int i = 0, sum = 0;
    while (sum &lt; n) {
        sum += ++i;
    }
    return i;
}
</code></span></code></pre>
<p>
<script type="math/tex">\cfrac{t*(t+1)}{2} \lt n</script>，结果为<script type="math/tex">O(\sqrt{n})</script>
</p>
<p><strong>6.【2019年统考真题】下列程序段的时间复杂度是</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">x = 0;
while (n &gt;= (x+1)*(x+1)) {
    x = x + 1;
}
</code></span></code></pre>
<p>
<script type="math/tex">(x+1)^2 \le n</script>，结果为<script type="math/tex">O(\sqrt{n})</script>
</p>
<h2 id="_4">第二章 线性表</h2>
<h3 id="2">2、线性表的顺序表示</h3>
<h3 id="3">3、线性表的链式表示</h3>
<h4 id="1_1">1）单向链表</h4>
<h4 id="2_1">2）双向链表</h4>
<h4 id="3_1">3）循环链表</h4>
<h4 id="4">4）静态链表</h4>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">typedef struct {
    ElemType data;
    int next;
} SlinkList[MaxSize];
</code></span></code></pre>
<p>借助数组来描述线性表的链式存储结构，需要预先分配一块连续的存储空间，同时还具有链表的优点，删除和添加元素不需要移动元素。</p>
<h3 id="_5">知识点</h3>
<p><strong>1.【2016年统考真题】已知一个带有表头结点的双向循环链表L，结点结构为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>[prev][data][next]</code></span>。现要删除指针p所指向的结点，正确的语句顺序是【D】</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">A. p-&gt;next-&gt;prev = p-&gt;prev; p-&gt;prev-&gt;next = p-&gt;prev; free(p);
B. p-&gt;next-&gt;prev = p-&gt;next; p-&gt;prev-&gt;next = p-&gt;next; free(p);
C. p-&gt;next-&gt;prev = p-&gt;next; p-&gt;prev-&gt;next = p-&gt;prev; free(p);
D. p-&gt;next-&gt;prev = p-&gt;prev; p-&gt;prev-&gt;next = p-&gt;next; free(p);
</code></span></code></pre>
<p>2.给定有n个元素的一维数组，建立一个有序链表的最低时间复杂度是【<script type="math/tex">O(n\log_2n)</script>】：先排序<script type="math/tex">O(n\log_2n)</script>，再创建链表<script type="math/tex">O(n)</script>
</p>
<p>3.某线性表用<strong>带头结点</strong>的<strong>循环单链表</strong>结构，头指针为<span style="overflow-x: auto; max-width:100%; display:inline;"><code>head</code></span>，当<span style="overflow-x: auto; max-width:100%; display:inline;"><code>head-&gt;next-&gt;next = head</code></span>成立时，线性表的长度可能是【0或1】.</p>
<h2 id="_6">第三章 栈和队列</h2>
<h3 id="1_2">1、栈</h3>
<h4 id="1_3">1）顺序栈</h4>
<h4 id="2_2">2）共享栈</h4>
<h4 id="3_2">3）链式栈</h4>
<h3 id="2_3">2、栈的应用</h3>
<h4 id="1_4">1）栈在括号匹配</h4>
<h4 id="2_4">2）栈在表达式求值</h4>
<blockquote class="content-quote">
<p>本人编写的一个逆波兰表达式计算器：<a href="https://github.com/zromyk/Calculator">https://github.com/zromyk/Calculator</a></p>
</blockquote>
<p>将一个普通的<strong>中缀表达式</strong>转换为<strong>逆波兰表达式</strong>的一般算法是：</p>
<p>首先需要分配2个栈：</p>
<ol>
<li>一个作为临时存储运算符的栈S1</li>
<li>一个作为存放逆波兰式的栈S2</li>
</ol>
<p>从中缀式的左端开始取字符，逐序进行如下步骤：</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>取出的字符</th>
<th>操作</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>操作数</td>
<td>分析出完整的运算数，该操作数直接送入S2栈。</td>
</tr>
<tr>
<td>2</td>
<td>(</td>
<td>直接送入S1栈顶。</td>
</tr>
<tr>
<td>3</td>
<td>)</td>
<td>将距离S1栈栈顶最近的&rsquo;(&lsquo;之间的运算符，逐个出栈，依次送入S2栈，此时抛弃&rsquo;(&lsquo;。</td>
</tr>
<tr>
<td>4</td>
<td>运算符</td>
<td>将该运算符与S1栈栈顶运算符（包括左括号）比较：<br />运算符优先级 <script type="math/tex">\gt</script> S1栈栈顶运算符优先级，将该运算符进S1栈。<br />运算符优先级 <script type="math/tex">\le</script> S1栈栈顶运算符优先级，将S1栈的栈顶运算符弹出，送入S2栈中，最后将该运算符送入S1栈。</td>
</tr>
<tr>
<td>5</td>
<td></td>
<td>重复上面的1~4步，直至处理完所有的输入字符。</td>
</tr>
<tr>
<td>E</td>
<td>END</td>
<td>将S1栈内所有运算符逐个出栈，依次送入S2栈。</td>
</tr>
</tbody>
</table></div>
<p>【2014年考研408第2题】有出现该题。</p>
<h4 id="3_3">3）栈在递归</h4>
<h3 id="3_4">3、队列</h3>
<h4 id="1_5">1）顺序队列（不实用）</h4>
<h4 id="2_5">2）循环顺序队列</h4>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c">初始：Q.front = Q.rear = 0;
队首指针进1：Q.front = (Q.front + 1) % MaxSize;
队首指针进1：Q.rear  = (Q.rear  + 1) % MaxSize;
队列长度：(Q.rear - Q.front + MaxSize) % MaxSize;

队满条件：(Q.rear + 1) % MaxSize = Q.front;
队空条件：Q.front == Q.rear;
</code></span></code></pre>
<ol>
<li>牺牲一个单元来区分队空和队满，入队时少用一个队列单元。</li>
<li>队头指针在队尾指针的下一位置作为队满的标志。</li>
</ol>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/7B045DB38B638BDDE9FF00F89EFD50B1.jpg" alt="7B045DB38B638BDDE9FF00F89EFD50B1" style="zoom:80%;" /></p>
<h4 id="3_5">3）队列的链式存储</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>不带头结点的链式队列</th>
<th>带头结点的链式队列</th>
</tr>
</thead>
<tbody>
<tr>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/F51B383B4251045F2BD8B5114A106A18.jpg" alt="F51B383B4251045F2BD8B5114A106A18" style="zoom:67%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/2CB8D8A19E4F63F534D2D43A82F33FC5.jpg" alt="2CB8D8A19E4F63F534D2D43A82F33FC5" style="zoom:80%;" /></td>
</tr>
</tbody>
</table></div>
<h4 id="4_1">4）双端队列</h4>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/E1007102B4A9A2C7E67892578308E5C9-6492677.jpg" alt="E1007102B4A9A2C7E67892578308E5C9" style="zoom:18%;" /></p>
<h3 id="4_2">4、队列的应用</h3>
<h4 id="1_6">1）队列在层次遍历</h4>
<h4 id="2_6">2）队列在计算机系统</h4>
<h3 id="5">5、特殊矩阵的压缩存储</h3>
<h4 id="1_7">1）对称矩阵</h4>
<p>
<script type="math/tex; mode=display">
\left[\begin{array}{}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{n1}&a_{n2}&\cdots&a_{nn}\\
\end{array}\right]
</script>
</p>
<h4 id="2_7">2）三角矩阵</h4>
<p>
<script type="math/tex; mode=display">
\left[\begin{array}{}
a_{11}&a_{12}&\cdots&a_{1n}\\
      &a_{22}&\cdots&a_{2n}\\
      &      &\ddots&\vdots\\
      &      &      &a_{nn}\\
\end{array}\right]
\left[\begin{array}{}
a_{11}&      &      &      \\
a_{21}&a_{22}&      &      \\
\vdots&\vdots&\ddots&      \\
a_{n1}&a_{n2}&\cdots&a_{nn}\\
\end{array}\right]
</script>
</p>
<h4 id="3_6">3）三对角矩阵</h4>
<p>
<script type="math/tex; mode=display">
\left[\begin{array}{}
a_{1,1}&a_{1,2}&      &      &      \\
a_{2,1}&a_{2,2}&a_{2,2}&      &      \\
      &\ddots&\ddots&\ddots&      \\
      &      &a_{n-1,n-2}&a_{n-1,n-1}&a_{n-1,n}\\
      &      &      &a_{n,n-1}&a_{n,n}\\
\end{array}\right]
</script>
</p>
<h4 id="4_3">4）稀疏矩阵</h4>
<h5 id="1_8">（1）三元组（行，列，值）</h5>
<h5 id="2_8">（2）十字链表</h5>
<h3 id="_7">知识点</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>2.【2009年统考真题】设栈S和队列Q的初始状态均为空，元素<script type="math/tex">abcdefg</script>依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是<script type="math/tex">bdcfeag</script>，则栈S的容量至少是【3】<br /><br />&gt; <script type="math/tex">ab</script><br />&gt; <script type="math/tex">acd</script><br />&gt; <script type="math/tex">ac</script><br />&gt; <script type="math/tex">aef</script><br />&gt; <script type="math/tex">ae</script><br />&gt; <script type="math/tex">a</script><br />&gt; <script type="math/tex">g</script>
</td>
</tr>
<tr>
<td>1.【2010年统考真题】若元素<script type="math/tex">a,b,c,d,e,f</script>依次入栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是【D】<br /><br />&gt; A. <script type="math/tex">dcebfa</script><br />&gt; B. <script type="math/tex">cbdaef</script><br />&gt; C. <script type="math/tex">bcaefd</script><br />&gt; D. <script type="math/tex">afedcb</script>（<script type="math/tex">edcb</script>为连续的4次出栈操作）</td>
</tr>
<tr>
<td>8.【2010统考真题】某队列允许在两端进行入队操作，但是只允许在一段进行出队操作，若元素<script type="math/tex">a,b,c,d,e</script>依次进入此队列后再进行出队操作，则<strong>不可能</strong>得到的出队序列是【C】<br /><br />&gt; A. <script type="math/tex">b,a,c,d,e</script><br />&gt; B. <script type="math/tex">d,b,a,c,e</script><br />&gt; C. <script type="math/tex">d,b,c,a,e</script><br />&gt; D. <script type="math/tex">e,c,b,a,d</script><br /><br />解法1：遍历<br /><br /><script type="math/tex">a</script><br /><script type="math/tex">ab;ba</script><br /><script type="math/tex">cab,abc;cba,bac</script><br /><script type="math/tex">dcab,cabd;dabc,abcd;dcba,cbad;dbac,bacd</script><br /><br />解法2：因为<script type="math/tex">a,b</script>连续入队，因此<script type="math/tex">a,b</script>必定连续出队，C选项不符合</td>
</tr>
<tr>
<td>6.【2011统考真题】已知循环队列存储在一维数组A[0&hellip;n-1]中，且队列非空时front和rear分别指向<strong>队头元素</strong>和<strong>队尾元素</strong>。若初始时队列为空，且要求第一个进入队列的元素出存在A[0]处，则初始时front和rear的值分别为【0，n-1】<br /><br />&gt; 当第一个元素入队时，需要在front处放置元素，并且将rear进1，因此，他们的初值分别为0，n-1</td>
</tr>
<tr>
<td>3.【2013年统考真题】一个栈的入栈序列为<script type="math/tex">1,2,3,...,n</script>，出栈序列为<script type="math/tex">P_1,3,P_3,...,P_n</script>，则<script type="math/tex">P_3</script>可能的取值的个数为【<script type="math/tex">n-1</script>】<br /><br />&gt; 除了3之外都可取。</td>
</tr>
<tr>
<td>4.【2014年统考真题】元素<script type="math/tex">a,b,c,d,e</script>依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是【4】<br /><br />&gt; <script type="math/tex">d(e)c(e)b(e)a(e)</script>
</td>
</tr>
<tr>
<td>7.【2014统考真题】循环队列放在一维数组A[0&hellip;n-1]中，end1指向<strong>队头元素</strong>，end2指向<strong>队尾元素的后一个位置</strong>。假设队列的两端均可以进行入队和出队操作，队列中至多有M-1个元素，初始时为空。则<br /><br />&gt; 队空：end1=end2，队满：end1=(end2+1) mod M</td>
</tr>
<tr>
<td>10.【2016统考真题】设又如下图所示的火车车轨，入口到出口之间有n条隧道，列车的行进方向均为从左到右，列车可能驶入任意一条轨道。现有编号为1～9的9列火车，驶入的次序依次是8，4，2，5，3，9，1，6，7。若期望驶出的次序依次为1～9，则n至少是【4】<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-12-07 13.50.30.png" alt="截屏2020-12-07 13.50.30" style="zoom:50%;" /><br /><br />761935248 <script type="math/tex">\to</script> 进过n个轨道 <script type="math/tex">\to</script> 987654321<br /><br />&gt; 分析：8，入队，此时不能出队，占用第1个轨道。<br />&gt; 4，入队，此时不能出队，不能在8所在轨道上，占用第2个轨道。<br />&gt; 2，入队，此时不能出队，不能在4、8所在轨道上，占用第3个轨道。<br />&gt; 5，入队，可以在4所在轨道上。<br />&gt; 3，入队，可以在2所在轨道上。<br />&gt; 9，入队，可以在8所在轨道上。<br />&gt; 1，入队，需要立马出队，需要第4个轨道。<br />&gt; 6、7，方案众多。<br /><br />&gt; 结果至少需要4个轨道。</td>
</tr>
<tr>
<td>10.【2016统考真题】有一个100阶的<strong>三对角矩阵</strong>M，其元素<script type="math/tex">m_{i,j}(1\le i,j \le 100)</script>按行优先依次压缩存储在<strong>下标从0开始</strong>的一维数组中。元素<script type="math/tex">m_{30,30}</script>的下标是【87】<br /><br />&gt; 第1到29行的元素个数：<script type="math/tex">2+(29-2+1)*3=86</script>，第30行，<script type="math/tex">m_{30,29}</script>的下标是86，<script type="math/tex">m_{30,30}</script>的下标是87</td>
</tr>
<tr>
<td>5.【2017年统考真题】下列关于栈的叙述中，<strong>错误</strong>的是<br /><br />&gt; ✘ I. 采用非递归方式重写递归程序时必须使用栈<br />&gt; II. 函数调用时，系统要用栈保存必要信息<br />&gt; ✘ III. 只要确定了入栈次序，即可确定出栈顺序<br />&gt; ✘ IV. 栈是一种受限的线性表，允许其在<strong>两端操作</strong></td>
</tr>
<tr>
<td>11.【2017年统考真题】适用于压缩存储稀疏矩阵的两种存储结构是【<strong>三元组表</strong>和<strong>十字链表</strong>】</td>
</tr>
<tr>
<td>9.【2018统考真题】现有队列Q与栈S，初始时Q中的元素依次是1，2，3，4，5，6（1在队头），S为空。若允许下面三种操作：1.出队并输出元素，2.出队并将出队元素入栈，3.出栈并输出元素，则不能得到的输出序列是【C】<br /><br />&gt; A. <script type="math/tex">1,2,5,6,4,3</script><br />&gt; B. <script type="math/tex">2,3,4,5,6,1</script><br />&gt; C. <script type="math/tex">3,4,5,6,1,2</script><br />&gt; D. <script type="math/tex">6,5,4,3,2,1</script>
</td>
</tr>
<tr>
<td>12.【2018年统考真题】设有一个12X12的对称矩阵M，将其上三角部分的元素<script type="math/tex">m_{i,j}(1\le i,j \le 100)</script>按行优先依次压缩存储在C与颜色一位数组N中。元素<script type="math/tex">m_{6,6}</script>在N中的下标是【50】<br /><br />&gt; 第1到5行的元素个数：<script type="math/tex">12+11+10+9+8=50</script>，第6行，<script type="math/tex">m_{6,6}</script>的下标是50</td>
</tr>
</tbody>
</table></div>
<h2 id="_8">第四章 串</h2>
<h3 id="1_9">1、串的模式匹配</h3>
<h4 id="kmp">KMP算法</h4>
<p>STEP1：计算模式串<span style="overflow-x: auto; max-width:100%; display:inline;"><code>S='abcac'</code></span>的PM值：</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>片段</th>
<th>前缀</th>
<th>后缀</th>
<th>交集</th>
<th>最长相等前后缀长度（PM值）</th>
</tr>
</thead>
<tbody>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>'a'</code></span></td>
<td>空集</td>
<td>空集</td>
<td>空集</td>
<td>0</td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>'ab'</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{a}</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{b}</code></span></td>
<td>空集</td>
<td>0</td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>'abc'</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{a,ab}</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{bc,c}</code></span></td>
<td>空集</td>
<td>0</td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>'abca'</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{a,ab,abc}</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{bca,ca,a}</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{a}</code></span></td>
<td>1</td>
</tr>
<tr>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>'abcac'</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{a,ab,abc,abca}</code></span></td>
<td><span style="overflow-x: auto; max-width:100%; display:inline;"><code>{bcac,cac,ac,c}</code></span></td>
<td>空集</td>
<td>0</td>
</tr>
</tbody>
</table></div>
<p>STEP2：得到next表</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>编号</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
</tr>
</thead>
<tbody>
<tr>
<td>S</td>
<td>a</td>
<td>b</td>
<td>c</td>
<td>a</td>
<td>c</td>
</tr>
<tr>
<td>PM</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>next</td>
<td>-1</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>next（序列从1开始）</td>
<td>0</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>2</td>
</tr>
</tbody>
</table></div>
<h3 id="_9">知识点</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2015统考真题】已知字符串<span style="overflow-x: auto; max-width:100%; display:inline;"><code>S='abaabaabacacaabaabcc'</code></span>，模式串<span style="overflow-x: auto; max-width:100%; display:inline;"><code>T='abaabc'</code></span>，采用KMP算法进行匹配，第一次出现失配（<span style="overflow-x: auto; max-width:100%; display:inline;"><code>s[i]!=t[j]</code></span>）时<span style="overflow-x: auto; max-width:100%; display:inline;"><code>i=j=5</code></span>，则下次开始匹配时，i和j的值分别为【C】<br /><br />&gt; A. <span style="overflow-x: auto; max-width:100%; display:inline;"><code>i=1,j=0</code></span><br />&gt; B. <span style="overflow-x: auto; max-width:100%; display:inline;"><code>i=5,j=0</code></span><br />&gt; C. <span style="overflow-x: auto; max-width:100%; display:inline;"><code>i=5,j=2</code></span><br />&gt; D. <span style="overflow-x: auto; max-width:100%; display:inline;"><code>i=6,j=2</code></span><br /><br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.abaab aabacacaabaabcc</code></span><br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.abaab c</code></span><br /><br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.abaab aabacacaabaabcc</code></span><br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.\\\ab aabc</code></span></td>
</tr>
<tr>
<td>2.【2019统考真题】设主串<span style="overflow-x: auto; max-width:100%; display:inline;"><code>T='abaabaabcabaabc'</code></span>，模式串<span style="overflow-x: auto; max-width:100%; display:inline;"><code>S='abaabc'</code></span>，采用KMP算法进行模式匹配，到匹配成功为止，在匹配过程中的单个字符间的比较次数是【10】<br /><br />第一次到匹配失败，一共匹配比较6次：<br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.abaab aabcabaabc</code></span><br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.abaab c</code></span><br />第二次到匹配成功，一共匹配比较4次：<br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.abaab aabcabaabc</code></span><br /><span style="overflow-x: auto; max-width:100%; display:inline;"><code>.\\\ab aabc</code></span><br /></td>
</tr>
</tbody>
</table></div>
<h2 id="_10">第五章 树与二叉树</h2>
<h3 id="0">0、二叉树的定义</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>满二叉树</th>
<th>完全二叉树</th>
</tr>
</thead>
<tbody>
<tr>
<td>高度为<script type="math/tex">h</script>，且含有<script type="math/tex">2^h-1</script>个结点的二叉树，称为满二叉树。</td>
<td>高度为<script type="math/tex">h</script>，且含有<script type="math/tex">n</script>个结点的二叉树，当且仅当其每个结点都与高度为<script type="math/tex">h</script>的满二叉树中编号为<script type="math/tex">1\sim n</script>的结点一一对应是，称为完全二叉树。</td>
</tr>
<tr>
<td><img class="pure-img" alt="截屏2020-11-26 15.14.22" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 15.14.22.jpg" /></td>
<td><img class="pure-img" alt="截屏2020-11-26 15.16.29" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 15.16.29.jpg" /></td>
</tr>
</tbody>
</table></div>
<h3 id="1_10">1、二叉树的遍历</h3>
<h4 id="1_11">1）二叉树的遍历（前、中、后）</h4>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/DBBDCBB46D5C647A781C0C1DDA9092D0.jpg" alt="DBBDCBB46D5C647A781C0C1DDA9092D0" style="zoom:67%;" /></p>
<h5 id="onon">二叉树的遍历（递归，<script type="math/tex">O(n),O(n)</script>）</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;int&gt; preorder_inorder_postorder_Traversal(TreeNode* root) {
        vector&lt;int&gt; v;
        if (root == nullptr) { return v; }
        preorder(v, root);      // 1
        // inorder(v, root);    // 2
        // postorder(v, root);  // 3
        return v;
    }

    void preorder(vector&lt;int&gt; &amp;v, TreeNode* root) {
        v.push_back(root-&gt;val);
        if (root-&gt;left)  { preorder(v, root-&gt;left);  }
        if (root-&gt;right) { preorder(v, root-&gt;right); }
    }

    void inorder(vector&lt;int&gt; &amp;v, TreeNode* root) {
        if (root-&gt;left)  { inorder(v, root-&gt;left);  }
        v.push_back(root-&gt;val);
        if (root-&gt;right) { inorder(v, root-&gt;right); }
    }

    void postorder(vector&lt;int&gt; &amp;v, TreeNode* root) {
        if (root-&gt;left)  { inorder(v, root-&gt;left);  }
        if (root-&gt;right) { inorder(v, root-&gt;right); }
        v.push_back(root-&gt;val);
    }
};
</code></span></code></pre>
<h5 id="onon_1">二叉树的遍历（迭代，<script type="math/tex">O(n),O(n)</script>）</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;int&gt; preorder_inorder_Traversal(TreeNode* root) {
        // vector&lt;int&gt; preorder_v;  // 1
        // vector&lt;int&gt; inorder_v;   // 2
        stack&lt;TreeNode*&gt; s;

        while (root != nullptr || !s.empty()) {
            while (root != nullptr) {
                // preorder_v.push_back(root-&gt;val); // 1 preorder add
                s.push(root);
                root = root-&gt;left;
            }
            root = s.top();
            s.pop();
            // inorder_v.push_back(root-&gt;val);      // 2 inorder add
            root = root-&gt;right;
        }
        // return preorder_v;  // 1
        // return inorder_v;   // 2
    }

    vector&lt;int&gt; postorderTraversal(TreeNode* root) {
        vector&lt;int&gt; postorder_v; // 3
        stack&lt;TreeNode*&gt; s;
        TreeNode* prev = nullptr;

        while (root != nullptr || !s.empty()) {
            while (root != nullptr) {
                s.push(root);
                root = root-&gt;left;
            }
            root = s.top();
            // 当前节点无右子树
            // prev 作用于从右子节点退回母节点时，记录右子节点，防止又一次进入 else
            if (root-&gt;right == nullptr || root-&gt;right == prev) {
                s.pop();
                // postorder_v.push_back(root-&gt;val);    // 2 postorder add
                prev = root;
                root = nullptr;
            }
            else {
                root = root-&gt;right;
            }
        }
        return postorder_v; // 3
    }
};
</code></span></code></pre>
<h5 id="morrisono1">二叉树的遍历（morris，<script type="math/tex">O(n),O(1)</script>）</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/*
    如果 cur 无左孩子，cur 向右移动（cur = cur-&gt;right）
    如果 cur 有左孩子，找到 cur 左子树上最右的节点，记为 mright
        如果 mright 的 right 指针指向空，让其指向 cur，cur 向左移动（cur = cur.left）
        如果 mright 的 right 指针指向 cur，让其指向空，cur 向右移动（cur = cur.right）
*/
class Solution {
public:
    vector&lt;int&gt; preorderTraversal(TreeNode *root) {
        vector&lt;int&gt; v;
        TreeNode *cur = root;
        TreeNode *mright = nullptr;

        while (cur != nullptr) {
            // 如果 cur 无左孩子，cur 向右移动（cur = cur-&gt;right）
            if (cur-&gt;left == nullptr) {
                v.push_back(cur-&gt;val); // add
                cur = cur-&gt;right;
            } // 如果 cur 有左孩子，找到 cur 左子树上最右的节点，记为 mright
            else {
                mright = cur-&gt;left;
                while (mright-&gt;right != nullptr &amp;&amp; mright-&gt;right != cur) {
                    mright = mright-&gt;right;
                }
                // 如果 mright 的 right 指针指向空，让其指向 cur，cur 向左移动（cur = cur.left）
                if (mright-&gt;right == nullptr) {
                    mright-&gt;right = cur;
                    v.push_back(cur-&gt;val); // add
                    cur = cur-&gt;left;
                } // 如果 mright 的 right 指针指向 cur，让其指向空，cur 向右移动（cur = cur.right）
                else {
                    mright-&gt;right = nullptr;
                    cur = cur-&gt;right;
                }
            }
        }
        return v;
    }
};
</code></span></code></pre>
<h4 id="2_9">2）三种遍历方式的关系</h4>
<ol>
<li>
<p>知道<strong>中序遍历序列</strong> + <strong>先序遍历序列</strong>（或者<strong>后序遍历序列</strong>），可以唯一确定一颗树。</p>
<blockquote class="content-quote">
<p>因为先序遍历在一个区间中，第一个一定是根节点，后序遍历中最后一个一定是根节点，那么这个<strong>区间就由中序遍历给出</strong>，已知根节点，在中序遍历中找到相应位置，左边数组一定位于左子树，右边数组一定位于右子树中。</p>
</blockquote>
</li>
<li>
<p>先序遍历序列XY + 后序遍历序列YX，可以确定X是Y的祖先。</p>
</li>
</ol>
<h4 id="3_7">3）层次遍历</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>层次遍历</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/B2A71E5E3A929B916286BF3D6B3E0CF8.jpg" alt="B2A71E5E3A929B916286BF3D6B3E0CF8" style="zoom:40%;" /></td>
<td><strong>借助队列</strong>。<br />1. 将二叉树根结点入队；<br /><script type="math/tex">while (队列不为空) \{</script><br />2. 出队，访问出队结点；<br />3. 若有左子树，将左子树根结点入队；<br />4. 若有右子树，将右子树根结点入队；<br /><script type="math/tex">\}</script>
</td>
</tr>
</tbody>
</table></div>
<h4 id="4_4">4）深度优先遍历和广度优先遍历</h4>
<p>树的深度优先遍历（即树的先序遍历，先进去的后出来）利用<strong>栈</strong>，先压<strong>右</strong>子树，再压<strong>左</strong>子树。</p>
<p>树的广度优先遍历（即树的层次遍历，先进去的先出来）利用<strong>队列</strong>，先压<strong>左</strong>子树，再压<strong>右</strong>子树。</p>
<h3 id="2_10">2、线索二叉树</h3>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    bool ltag, rtag;
}
</code></span></code></pre>
<p>线索二叉树中，结点的前后线索指向对应遍历方式的前驱和后驱。（2014年考研408第4题）</p>
<blockquote class="content-quote">
<p>如：若中序遍历为ABCXDEF，则X的前驱指向C，后驱指向D.</p>
</blockquote>
<h3 id="3_8">3、树、森林</h3>
<h4 id="1_12">1）表示方法</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>双亲表示法</th>
<th>孩子表示法</th>
</tr>
</thead>
<tbody>
<tr>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-24 18.05.47.jpg" alt="截屏2020-11-24 18.05.47" style="zoom:33%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-24 18.09.20.jpg" alt="截屏2020-11-24 18.09.20" style="zoom:33%;" /></td>
</tr>
</tbody>
</table></div>
<h4 id="2_11">2）森林与二叉树的转换</h4>
<p>（2014年考研408第5题）</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>森林</th>
<th>变换过程</th>
<th>树</th>
</tr>
</thead>
<tbody>
<tr>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-23 22.20.08.jpg" alt="截屏2020-11-23 22.20.08" style="zoom:33%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-23 22.23.19.jpg" alt="截屏2020-11-23 22.23.19" style="zoom:33%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-23 22.28.48.jpg" alt="截屏2020-11-23 22.28.48" style="zoom:33%;" /></td>
</tr>
</tbody>
</table></div>
<h4 id="3_9">3）森林的遍历</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>森林</th>
<th>二叉树</th>
</tr>
</thead>
<tbody>
<tr>
<td>先根遍历</td>
<td>先序遍历</td>
</tr>
<tr>
<td>后根遍历</td>
<td>中序遍历</td>
</tr>
</tbody>
</table></div>
<h4 id="4_5">4）树的应用——并查集</h4>
<h3 id="4_6">4、树与二叉树的应用</h3>
<h4 id="1_13">1）二叉排序树</h4>
<ol>
<li>中序遍历：左子树、根、右子树</li>
<li>二叉排序树：左子树 &lt; 根 &lt; 右子树</li>
<li>中序遍历序列是一个递增的有序序列</li>
</ol>
<h4 id="2avl">2）平衡二叉树（AVL）</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>LL旋转（右旋）</th>
<th>RR旋转（左旋）</th>
</tr>
</thead>
<tbody>
<tr>
<td><img class="pure-img" alt="IMG_6553" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6553.jpg" /></td>
<td><img class="pure-img" alt="IMG_6551" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6551.jpg" /></td>
</tr>
<tr>
<td><img class="pure-img" alt="截屏2020-11-26 16.08.13" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 16.08.13.jpg" /></td>
<td><img class="pure-img" alt="截屏2020-11-26 16.07.55" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 16.07.55.jpg" /></td>
</tr>
<tr>
<td></td>
<td></td>
</tr>
<tr>
<td><strong>LR旋转</strong></td>
<td><strong>RL旋转</strong></td>
</tr>
<tr>
<td><img class="pure-img" alt="IMG_6552" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6552.jpg" /></td>
<td><img class="pure-img" alt="IMG_6554" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6554.jpg" /></td>
</tr>
<tr>
<td><img class="pure-img" alt="截屏2020-11-26 16.08.26" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 16.08.26.jpg" /></td>
<td><img class="pure-img" alt="截屏2020-11-26 16.10.34" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 16.10.34-6378275.jpg" /></td>
</tr>
</tbody>
</table></div>
<h4 id="3_10">3）哈夫曼树和哈夫曼编码</h4>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/41815183E1442829993F7DAACE697957.jpg" alt="41815183E1442829993F7DAACE697957" style="zoom:33%;" /><br />
<script type="math/tex; mode=display">
\begin{equation}\begin{split} 
(a)WPL&=   &\ +\ &2*(7+5+2+4)&\ +\ &       \ &=\ 36 \\
(b)WPL&=1*2&\ +\ &        2*4&\ +\ &3*(7+5)\ &=\ 46 \\
(c)WPL&=1*1&\ +\ &        2*5&\ +\ &3*(2+4)\ &=\ 35
\end{split}\end{equation}
</script>
</p>
<h5 id="1_14">1. 哈夫曼树</h5>
<p>用构造哈夫曼树的过程生成的二进制<strong>前缀编码</strong>。哈夫曼树是一类<strong>带权路径长度最短</strong>的树。</p>
<h5 id="2_12">2. 前缀编码</h5>
<p>如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称该编码是前缀编码。【2014年考研408第6题】</p>
<h3 id="_11">树的性质</h3>
<ol>
<li><strong>树中的结点数等于所有结点的度数+1（边的总数+1）</strong></li>
<li>度为<script type="math/tex">m</script>的树中第<script type="math/tex">i</script>层上至多有<script type="math/tex">m^{i-1}</script>个结点</li>
<li>高度为<script type="math/tex">h</script>的<script type="math/tex">m</script>叉树至多有<script type="math/tex">\cfrac{m^h-1}{m-1}</script>个结点</li>
<li>具有<script type="math/tex">n</script>个结点的<script type="math/tex">m</script>叉树的最小高度为<script type="math/tex">\lceil \log_m(n(m-1)+1) \rceil</script>
</li>
</ol>
<h3 id="_12">知识点（树的结点个数）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1. 树最适合用来表示【元素之间具有分支层次关系】的数据。</td>
</tr>
<tr>
<td>2. 一颗有n个结点的树的所有结点的度数之和为【n-1】</td>
</tr>
<tr>
<td><strong>3.【2009年统考真题】已知一颗完全二叉树的第六层（设根为第一层）有8个叶结点，则该完全二叉树的结点个数最多是【111】</strong><br /><br />&gt; 按6层计算：<script type="math/tex">1+2+4+8+16+8=39</script>错误<br /><strong>&gt; 按7层计算：</strong><script type="math/tex">1+2+4+8+16+32+48(64-8*2)=111</script>
</td>
</tr>
<tr>
<td><strong>4.【2010年统考真题】在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点的个数是【82】</strong><br /><br />&gt; 叶结点即为度为0的结点<br />&gt; 总度数：<script type="math/tex">20*4+10*3+1*2+10*1+n*0=122</script><br />&gt; 当前结点数：<script type="math/tex">20+10+1+10=41</script><br />&gt; <script type="math/tex">总结点数=度数+1</script><br />&gt; 剩下即为度为0的（叶结点）数n：<script type="math/tex">122+1-41=82</script>
</td>
</tr>
<tr>
<td>5.【2011统考真题】若一颗完全二叉树有768个结点，则该二叉树中叶结点的个数是【384】<br /><br />&gt; 高度为9的满二叉树的结点个数：<script type="math/tex">2^9-1=512-1=511</script>个结点<br />&gt; 则第10层上叶结点的个数：<script type="math/tex">768-511=257</script>，<strong>！！注意：此时未结束！！</strong>还有第9层上的叶结点数未记录！！<br /><br />&gt; 第9层上的结点数为<script type="math/tex">2^9-2^8=256</script><br />&gt; 第10层上有<script type="math/tex">257</script>个叶结点，需要第9层上有<script type="math/tex">257/2=128.5\sim129</script>个<strong>分支结点</strong><br />&gt; 则第9层上的叶结点数为<script type="math/tex">256-129=127</script><br />&gt; **总共的叶结点数为<script type="math/tex">257+127=384</script>个！！！</td>
</tr>
<tr>
<td>6.【2016年考研408第5题】若森林F由15条边，25个结点，则F包含树的个数是【10】。<br /><br />&gt; <script type="math/tex">15+n=25</script><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-25 21.07.21.jpg" alt="截屏2020-11-25 21.07.21" style="zoom:33%;" /></td>
</tr>
<tr>
<td>7.【2018年统考真题】设一颗非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是【<script type="math/tex">2k-1</script>】</td>
</tr>
</tbody>
</table></div>
<h3 id="_13">知识点（树的遍历）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2009年统考真题】给定二叉树如右图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3175624，则其遍历方式是【RNL】<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 14.56.48.jpg" alt="截屏2020-11-29 14.56.48" style="zoom:25%;" /></td>
</tr>
<tr>
<td>2.【2011年统考真题】若一颗二叉树的前序遍历和后序遍历序列分别为1234和4321，则该二叉树的中序遍历<strong>不会</strong>是【C】<br /><br />&gt; A. 1234<br />&gt; B. 2341<br />&gt; 【C. 3241】<br />&gt; D. 4321<br /><br /><strong>&gt; 前序遍历 + 后序遍历不能确定唯一二叉树，但是可以确定谁是谁的祖先。<br />&gt; 前序遍历为：XY，后序遍历为：YX，可以确定X为Y的祖先。<br /></strong><br />&gt; 前序遍历 + 后序遍历：1234和4321，可以确定1是2、3、4的祖先。<br />&gt; 前序遍历 + 后序遍历：234和432，可以确定2是3、4的祖先。<br />&gt; 因此确定1和2只有1个孩子结点，故在中序遍历中1，2应该分别在片段的两侧。<br />&gt; 而在选项C中，片段324，2在3和4的中间，这是不可能的。</td>
</tr>
<tr>
<td>3.【2012年统考真题】若一颗饿叉树的前序遍历序例为aebdc，后序遍历序列为bcdea，则根结点的孩子结点【A】<br /><br />&gt; 【A. 只有e】<br />&gt; B. 有e、b<br />&gt; C. 有e、c<br />&gt; D. 无法确定<br /><br />&gt; 前序遍历 + 后序遍历：aebdc和bcdea可以确定a为bcde的祖先，a为根结点<br />&gt; 前序遍历 + 后序遍历：ebdc和bcde可以确定e为bdc的祖先<br />&gt; 则可知a只有e这一个孩子结点</td>
</tr>
<tr>
<td><strong>4.【2015年统考真题】先序序列为abcd的不同二叉树的个数是【14】<br /></strong><br />&gt; 根据二叉树前序遍历NLR和中序遍历LNR的递归算法中递归工作栈的状态变化得出：<br />&gt; 两者的关系相当于：以前序序列入栈，中序序列出栈<br />&gt; 对于n个不同的元素进栈，出栈序列的个数为<script type="math/tex">\cfrac{1}{n+1}C_{2n}^n</script><br />&gt; 结果为14</td>
</tr>
<tr>
<td>5.【2017年统考真题】某二叉树的树形如图，其后序序列为eacbdgf，树中与结点a同层的结点是【d】<br />由后序遍历序列推测的到树<img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 15.15.38.jpg" alt="截屏2020-11-29 15.15.38" style="zoom:33%;" /></td>
</tr>
<tr>
<td>6.【2017年统考真题】要使一颗非空二叉树的先序序列与中序序列相同，其所有非叶结点必须满足的条件是【只有右子树】<br /><br />&gt; 先序遍历，NLR，中序遍历，LNR<br />&gt; 当L为空的时候，两者相等。</td>
</tr>
<tr>
<td><strong>7.【2010，2013，2014统考真题】二叉树线索化，就是按照对应的遍历结果，让结点指向其前驱和后继结点。</strong></td>
</tr>
</tbody>
</table></div>
<h3 id="_14">知识点（二叉排序查找树）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2011统考真题】对于下列关键字序列，<strong>不可能</strong>构成某二叉排序树中一条查找路径的是【A】<br /><br />&gt; A. 95,22,<strong>91</strong>,<strong>24</strong>,<strong>94</strong>,71</td>
</tr>
<tr>
<td>2.【2013统考真题】在任意一颗<strong>非空二叉排序树</strong><script type="math/tex">T_1</script>中，删除某结点V之后形成二叉排序树<script type="math/tex">T_2</script>，再将v插入<script type="math/tex">T_2</script>形成二叉排序树<script type="math/tex">T_3</script>。下列关于<script type="math/tex">T_1</script>和<script type="math/tex">T_3</script>的叙述中，正确的是【II，III】<br /><br />&gt; I. 若v是<script type="math/tex">T_1</script>的叶结点，则<script type="math/tex">T_1</script>和<script type="math/tex">T_3</script>不同。<br />&gt; <strong>II. 若v是<script type="math/tex">T_1</script>的叶结点，则<script type="math/tex">T_1</script>和<script type="math/tex">T_3</script>相同。</strong><br />&gt; <strong>III. 若v是<script type="math/tex">T_1</script>的非叶结点，则<script type="math/tex">T_1</script>和<script type="math/tex">T_3</script>不同。</strong><br />&gt; IV. 若v是<script type="math/tex">T_1</script>的非结点，则<script type="math/tex">T_1</script>和$相同。<br /><br />》 需要注意的是，本题中的树为二叉排序树，不是平衡树，注意与【2019统考真题】中的AVL树相区别。</td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td></td>
</tr>
</tbody>
</table></div>
<h3 id="avl">知识点（平衡二叉树，AVL）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>0.【2009统考真题】在AVL树中，各个结点的平衡因子【<script type="math/tex">[-1,1]</script>】。</td>
</tr>
<tr>
<td>2.【2010统考真题】下图所示的平衡二叉树在插入关键字48之后，关键字37所在结点的左子结点和右子结点为【24和53】。<br /><br /><video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/avl.mov"></video></td>
</tr>
<tr>
<td>2.【2012统考真题】若平衡为叉树的高度为6，且所有非叶子结点的平衡因子均为1，则该平衡二叉树的结点总数为【20】。<br /></td>
</tr>
<tr>
<td>1.【2013年考研408第3题】若将关键字1，2，3，4，5，6，7依次插入到初始化为空的平衡二叉树T中，则T中平衡因子为0的<strong>分支结点</strong>的个数为【3】（查阅资料：分支结点(Branch Node)指度不为0的结点，也叫非终端结点或内部结点。即非叶子结点。）<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/0A7A690E653D2E35DAE039AA6F886B36.jpg" alt="截屏2020-11-26 19.54.26" style="zoom:40%;" /><br /><video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/2013.mov"></video></td>
</tr>
<tr>
<td>2.【2015统考真题】现有一颗无重复关键字的<strong>平衡二叉树</strong>，对其进行中序遍历可以得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是【D】<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 22.19.03.jpg" alt="截屏2020-11-29 22.19.03" style="zoom:33%;" /><br /> A. 根结点的度一定为2（考虑上面情形）<br />&gt; B. 树中最小元素一定是叶结点（考虑上面情形）<br />&gt; C. 最后插入的元素一定是叶结点（最后插入的元素可能导致二叉树不平衡，结果并不一定是叶结点）<br />&gt; 【D. 树中最大元素一定是无左子树】</td>
</tr>
<tr>
<td>3.【2018统考真题】已知二叉排序树如图，元素之间应满足的大小关系是【<script type="math/tex">x_1 \lt x_3 \lt x_5 \lt x_4 \lt x_2</script>】<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 22.21.30.jpg" alt="截屏2020-11-29 22.21.30" style="zoom:33%;" /></td>
</tr>
<tr>
<td>4.【2019统考真题】在任意一颗非空<strong>平衡二叉树</strong><script type="math/tex">T_1</script>中，删除某结点v之后形成平衡二叉树<script type="math/tex">T_2</script>，再将v插入<script type="math/tex">T_2</script>形成平衡二叉树<script type="math/tex">T_3</script>，下列关系中正确的是【I】<br /><br />&gt; I. 若v是<script type="math/tex">T_1</script>的叶结点，则<script type="math/tex">T_1</script>与<script type="math/tex">T_3</script>可能不相同<br />&gt; II. 若v不是<script type="math/tex">T_1</script>的叶结点，则<script type="math/tex">T_1</script>与<script type="math/tex">T_3</script>一定不相同<br />&gt; III. 若v不是<script type="math/tex">T_1</script>的叶结点，则<script type="math/tex">T_1</script>与<script type="math/tex">T_3</script>一定相同<br /><br />》 注意本题是平衡二叉树，删除叶结点后插入，可能导致二叉树不平衡，则<script type="math/tex">T_1</script>与<script type="math/tex">T_3</script>不相同<br />〉 删除非叶结点后插入，可能导致调整之后依然为原平衡二叉树</td>
</tr>
<tr>
<td>5.【2019统考真题】对于n个无不相同的符号进入哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是【58】<br /><br />&gt; <script type="math/tex">n+n-1=115</script>，结果<script type="math/tex">n=58</script>
</td>
</tr>
</tbody>
</table></div>
<h3 id="_15">知识点（最小带权路径树，哈夫曼）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1. 树的路径长度是从树<strong>根</strong>到每个结点的路径长度的【总和】</td>
</tr>
<tr>
<td>4.【2010年统考真题】<script type="math/tex">n(n\ge2)</script>个权值均不同的字符构成哈夫曼树，关于该树的叙述中，<strong>错误</strong>的是【A】<br /><br />&gt; A. 该树一定是一颗完全二叉树（很明显错误）<br />&gt; B. 树中一定没有度为1的结点<br />&gt; C. 树中两个权值最小的结点一定是兄弟结点<br />&gt; D. 树中任意非叶结点的权值一定不小于下一层任意结点的权值<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 21.43.09.jpg" alt="截屏2020-11-29 21.43.09" style="zoom:50%;" /></td>
</tr>
<tr>
<td>2.【2013年考研408第4题】已知三叉树T中6个结点的权分别是2，3，4，5，6，7，T的带权（外部）路径长度最小是【46】<br /><br />&gt; <script type="math/tex">(2+3)*3+(4+5)*2+(6+7)*1 = 15+18+13=46</script><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 19.37.37.jpg" alt="截屏2020-11-26 19.37.37" style="zoom:50%;" /></td>
</tr>
<tr>
<td>3. 在有n个叶子结点的哈夫曼树中，非叶子结点的总数是【n-1】</td>
</tr>
<tr>
<td>5.【2014年统考真题408第6题】5个字符有如下4种编码方案，不是前缀编码的是【D】<br /><br />&gt; A. <script type="math/tex">01,0000,0001,001,1</script><br />&gt; B. <script type="math/tex">011,000,001,010,1</script><br />&gt; C. <script type="math/tex">000,001,010,011,100</script><br />&gt; D. <script type="math/tex">0,100,\underline{110},1110,\underline{110}0</script><br /><br />》<strong>如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称该编码是前缀编码。</strong></td>
</tr>
<tr>
<td>6.【2015年统考真题】下列选项给出的是从根分别到达两个叶结点路径上的权值序列，属于同一棵哈夫曼树的是【D】<br /><br />&gt; A. <script type="math/tex">24,10,5和24,10,7</script>（<script type="math/tex">10+10\ne24且5+7\ne10</script>）<br />&gt; B. <script type="math/tex">24,10,5和24,12,7</script>（<script type="math/tex">10+12\ne24</script>）<br />&gt; C. <script type="math/tex">24,10,10和24,14,11</script>（<script type="math/tex">10,10</script>不正确）<br />&gt; D. <script type="math/tex">24,10,5和24,14,6</script>
</td>
</tr>
<tr>
<td>7.【2017统考真题】已知字符集<script type="math/tex">\{a,b,c,d,e,f,g,h\}</script>，各字符的哈夫曼编码依次是0100,10,000,0101,001,011,11,0001，则编码序列0100011001001011110101的译码结果为【afeefgd】<br /><br />&gt; <span style="overflow-x: auto; max-width:100%; display:inline;"><code>0100 011 001 001 011 11 0101</code></span><br />&gt; <span style="overflow-x: auto; max-width:100%; display:inline;"><code>a    f   e   e   f   g  d</code></span></td>
</tr>
<tr>
<td>8.【2018统考真题】已知字符集<script type="math/tex">\{a,b,c,d,e,f\}</script>，各字符揣选的次数分别为6,3,8,2,10,4，则对应字符集种个字符的哈夫曼编码是【】</td>
</tr>
</tbody>
</table></div>
<h3 id="_16">知识点（森林转化为树）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2009年统考真题】将森林转化为对应的二叉树，若在二叉树中，结点u是结点v的<strong>父结点的父结点</strong>，则在原来的森林中，u和v可能具有的关系是【I，II】<br /><br />&gt; I. 父子关系<br />&gt; II. 兄弟关系<br />&gt; III. u的父结点和v的父结点是兄弟关系<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 16.24.17.jpg" alt="截屏2020-11-29 16.24.17" style="zoom:33%;" /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 16.30.52.jpg" alt="截屏2020-11-29 16.30.52" style="zoom:33%;" /></td>
</tr>
<tr>
<td>2.【2011年统考真题】已知一颗有2011个结点的树，其叶结点的个数为116，该树对应的二叉树中无右孩子结点的结点个数为【1896】<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 16.37.59.jpg" alt="截屏2020-11-29 16.37.59" style="zoom:33%;" /><br />根据树转化为二叉树的方法：<br />&gt; 根结点和分支结点的最右边的孩子无右子树<br />&gt; 所以对应<strong>二叉树</strong>中无右孩子结点的结点数 = <strong>树</strong>中根结点数（即1）+ 分支结点数<br />&gt; 结果为：<script type="math/tex">1+(2011-116)=1896</script>
</td>
</tr>
<tr>
<td>3.【2014统考真题】将森林F转化为二叉树T，F中叶结点的个数等于【C】<br /><br />&gt; T中叶结点的个数<br />&gt; T中度为1的结点个数<br />&gt; T中左孩子指针为空的结点个数<br />&gt; T中右孩子指针为空的结点个数<br /><br />&gt; 分析：可利用上题中的图（第2题），结果选C<br />&gt; 另外：森林中的叶结点由于没有孩子（可能有兄弟），转化成树的时候没有左子树。<br />&gt; 其他结点因为有孩子，转为树的时候根据左孩子右兄弟原则，必定有左子树。</td>
</tr>
<tr>
<td>4.【2016年统考真题】若森林F有15条边，25个结点，则F包含树的个数是【10】<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 16.49.55.jpg" alt="截屏2020-11-29 16.49.55" style="zoom:33%;" /><br />&gt;设B、C、D&hellip;为森林的根<br />&gt; 添加一个A和n条边，使森林变成了一棵树<br />&gt; 树满足：<script type="math/tex">结点数 - 1 = 边数</script><br />&gt; <script type="math/tex">25 + 1(A) - 1 = 15 + n(添加边，即原来的树数)</script>，结果为<script type="math/tex">n=10</script>
</td>
</tr>
<tr>
<td>5.【2019年统考真题】森林的后根遍历与树的中序遍历相同。</td>
</tr>
</tbody>
</table></div>
<h2 id="_17">第六章 图</h2>
<h3 id="1_15">1、图的表示</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>无向图</th>
<th>有向图</th>
</tr>
</thead>
<tbody>
<tr>
<td>度数</td>
<td>
<script type="math/tex">边数 * 2</script>
</td>
<td>
<script type="math/tex">出度 + 入度</script>
</td>
</tr>
<tr>
<td>完全图</td>
<td><strong>任意</strong>两个顶点之间都存在边。<br /><script type="math/tex">n</script>个结点有<script type="math/tex">\cfrac{n(n-1)}{2}</script>条边</td>
<td><strong>任意</strong>两个顶点之间存在方向相反的弧。<br /><script type="math/tex">n</script>个顶点有<script type="math/tex">n(n-1)</script>条弧</td>
</tr>
<tr>
<td>连通</td>
<td><strong>任意</strong>两个节点之间都是<strong>连通</strong>的。<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 22.50.56.jpg" alt="截屏2020-11-29 22.50.56" style="zoom:67%;" /></td>
<td><strong>任意</strong>两个节点之间都是<strong>强连通</strong>的。<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 22.51.00.jpg" alt="截屏2020-11-29 22.51.00" style="zoom:67%;" /></td>
</tr>
<tr>
<td>子图</td>
<td><strong>1. 满足图的定义。</strong><br />2. 结点为图的子集，边也为图的子集。<br />（边集可以为空集合）</td>
<td><strong>1. 满足图的定义。</strong><br />2. 结点为图的子集，弧也为图的子集。<br />（弧集可以为空集合）</td>
</tr>
<tr>
<td>生成子图</td>
<td>包含图的所有结点。</td>
<td>包含图的所有结点。</td>
</tr>
<tr>
<td>极大连通子图</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 23.05.24.jpg" alt="截屏2020-11-29 23.05.24" style="zoom:50%;" /><br />连通子图且包含边最多，没有比他们更大的子图。</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 23.05.46.jpg" alt="截屏2020-11-29 23.05.46" style="zoom:50%;" /><br />连通子图且包含弧最多，没有比他们更大的子图。</td>
</tr>
<tr>
<td>极小联通子图</td>
<td>连通子图且包含边最少。</td>
<td></td>
</tr>
<tr>
<td>生成树</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 23.12.34.jpg" alt="截屏2020-11-29 23.12.34" style="zoom:50%;" /><br />1. 原图必须是<strong>连通图</strong>。<br />2. 生成树是包含全部顶点的一个<strong>极小连通图</strong>。<br />特点：n个顶点的生成树有n-1条边。<br />（生成树不一定唯一）</td>
<td></td>
</tr>
<tr>
<td>生成森林</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-29 23.15.53.jpg" alt="截屏2020-11-29 23.15.53" style="zoom:50%;" /><br />1. 原图必须是<strong>非连通图</strong>。<br />（生成树不一定唯一）</td>
<td></td>
</tr>
</tbody>
</table></div>
<h3 id="2_13">2、图的存储</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>表示法</th>
<th>无向图</th>
<th>有向图</th>
</tr>
</thead>
<tbody>
<tr>
<td>邻接矩阵</td>
<td>
<script type="math/tex; mode=display">A = \left[\begin{array}{} 出入&[1]&[2]&[3]&[4]\\ [1]&0&0&0&1 \\ [2]&0&0&1&0 \\ [3]&0&1&0&0 \\ [4]&1&0&0&0 \end{array}\right]</script>关于主对角线对称</td>
<td>
<script type="math/tex; mode=display">A = \left[\begin{array}{} 出入&[1]&[2]&[3]&[4]\\ [1]&0&1&0&1 \\ [2]&0&0&1&0 \\ [3]&0&1&0&1 \\ [4]&1&0&0&0 \end{array}\right]</script>
</td>
</tr>
<tr>
<td>邻接表</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6556.jpg" alt="IMG_6556" style="zoom:40%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6557.jpg" alt="IMG_6557" style="zoom:40%;" /></td>
</tr>
<tr>
<td>十字链表</td>
<td></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6558.jpg" alt="IMG_6558" style="zoom:40%;" /></td>
</tr>
<tr>
<td>邻接多重表</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6559.jpg" alt="IMG_6559" style="zoom:40%;" /></td>
<td></td>
</tr>
</tbody>
</table></div>
<h4 id="_18">网络的邻接矩阵表示法</h4>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6555.jpg" alt="IMG_6555" style="zoom:33%;" /></p>
<h3 id="3_11">3、图的遍历</h3>
<h4 id="1_16">1）广度优先搜索</h4>
<h4 id="2_14">2）深度优先搜索</h4>
<h4 id="3_12">3）图的连通性</h4>
<h3 id="4_7">4、图的应用</h3>
<h4 id="1_17">1）最小生成树</h4>
<p>求最短路径（无向图）</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>Prim算法</th>
<th>Kruskal算法</th>
</tr>
</thead>
<tbody>
<tr>
<td>注</td>
<td></td>
<td>当要求所有的最小生成树的时候，建议优先使用Kruskal算法。</td>
</tr>
<tr>
<td></td>
<td><img class="pure-img" alt="IMG_6584" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6584.jpg" /></td>
<td><img class="pure-img" alt="IMG_6585" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6585.jpg" /></td>
</tr>
<tr>
<td>算法</td>
<td><img class="pure-img" alt="截屏2020-11-30 15.35.51" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 15.35.51.jpg" /></td>
<td><img class="pure-img" alt="截屏2020-11-30 15.36.07" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 15.36.07.jpg" /></td>
</tr>
<tr>
<td>视频</td>
<td><video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" controls="controls" width=100% height="100%" src="/post/计算机考研-算法与数据结构.assets/Prim.mov"></video></td>
<td><video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" controls="controls" width=100% height="100%" src="/post/计算机考研-算法与数据结构.assets/Kruskal.mov"></video></td>
</tr>
<tr>
<td>时间复杂度</td>
<td>
<script type="math/tex">O(V^2)</script>，只和结点个数有关。</td>
<td>
<script type="math/tex">O(\log_2E)</script>，只和边条数有关。</td>
</tr>
<tr>
<td>优点</td>
<td>适合求解<strong>边稠密</strong>的图的最小生成树。</td>
<td>适合求解<strong>边稀疏</strong>的图的最小生成树。</td>
</tr>
<tr>
<td>说明</td>
<td></td>
<td>采用<strong>堆</strong>来存放边的集合。由于生成树T中所有边可以视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，因此可以采用<strong>并查集</strong>的结构来描述T。</td>
</tr>
</tbody>
</table></div>
<h4 id="2_15">2）最短路径</h4>
<p>（有向图）</p>
<p>路径的定义：由顶点和相邻顶点序偶构成的边所形成的序列。</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>Dijkstra算法</th>
<th>Floyd算法</th>
</tr>
</thead>
<tbody>
<tr>
<td>用途</td>
<td>求<strong>单源</strong>最短路径</td>
<td>求<strong>各顶点之间</strong>最短路径</td>
</tr>
<tr>
<td>算法</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 17.18.18.jpg" alt="截屏2020-11-30 17.18.18" style="zoom:50%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 17.25.21.jpg" alt="截屏2020-11-30 17.25.21" style="zoom:50%;" /></td>
</tr>
</tbody>
</table></div>
<h4 id="3_13">3）有向无环图描述表达式</h4>
<h4 id="4_8">4）拓扑排序</h4>
<h5 id="_19">有向无环图</h5>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>有向无环图</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>定义</td>
<td>若有一个有向图不存在环，则称为有向无环图，简称DAG图。</td>
</tr>
<tr>
<td>用途</td>
<td>实现对相同子式的共享，节省存储空间。</td>
</tr>
<tr>
<td>公式</td>
<td>
<script type="math/tex">((a+b)*(b*\underline{(c+d)})+\underline{\underline{(c+d)}*e})*(\underline{\underline{(c+d)}*e}))</script>
</td>
</tr>
<tr>
<td>图示</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/B740A6C208CA227E1844B7644AAC71F8.jpg" alt="B740A6C208CA227E1844B7644AAC71F8" style="zoom:50%;" /></td>
</tr>
</tbody>
</table></div>
<h5 id="_20">拓扑排序</h5>
<p>定义：在图论中，有一个有向无环图（DAG）的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：</p>
<ol>
<li>每个顶点只出现一次</li>
<li>若顶点A在序列中排在顶点B的前面，则在图汇总不存在从顶点B到顶点A的路径。</li>
</ol>
<p>做法：每次选择入度为0的结点，从图中删去，同时删去所有该顶点指出的边。【2014年考研408第7题】</p>
<h5 id="_21">逆拓扑排序</h5>
<p>做法：每次选择出度为0的结点，从图中删去，同时删去所有指入该顶点的边。</p>
<h4 id="5_1">5）关键路径</h4>
<h5 id="aoe">AOE网</h5>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>AOE网</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td>定义</td>
<td>若用DAG图表示一个工程，其顶点表示活动，用有向边<script type="math/tex"><V_i,V_j></script>表示活动<script type="math/tex">V_i</script>必须先于活动<script type="math/tex">V_j</script>进行的这样一种关系，则将这种有向图称为顶点表示活动图，即为AOE网。</td>
</tr>
<tr>
<td>图示</td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 20.08.42.jpg" alt="截屏2020-11-30 20.08.42" style="zoom:40%;" /></td>
</tr>
<tr>
<td>性质</td>
<td>1. 只有在进入某顶点的各有向边所代表的活动都<strong>结束</strong>时，该顶点代表的事件才能开始发生。</td>
</tr>
<tr>
<td></td>
<td>2. 只有在某顶点所有代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。</td>
</tr>
<tr>
<td>事件<script type="math/tex">v_k</script>最早发生时间<script type="math/tex">ve(k)</script>
</td>
<td>
<script type="math/tex">ve(源点)=0</script><br /><script type="math/tex">ve(k)=\max\{ve(j)+Weight(v_j,v_k)\}</script>，<script type="math/tex">v_k</script>为<script type="math/tex">v_j</script>的后继。</td>
</tr>
<tr>
<td>事件<script type="math/tex">v_k</script>最迟发生时间<script type="math/tex">vl(k)</script>
</td>
<td>
<script type="math/tex">vl(汇点)=ve(汇点)</script><br /><script type="math/tex">vl(k)=\min\{vl(j)-Weight(v_k,v_j)\}</script>，<script type="math/tex">v_k</script>为<script type="math/tex">v_j</script>的前继。</td>
</tr>
<tr>
<td></td>
<td>
<script type="math/tex; mode=display">\begin{array}{} V_k&V_1&V_2&V_3&V_4&V_5&V_6\\ \hline ve(k)&0&3&2&6&6&8 \\ vl(k)&0&4&2&6&7&8 \end{array}</script>
</td>
</tr>
<tr>
<td>活动<script type="math/tex">a_i</script>的最早发生时间<script type="math/tex">e(i)</script>
</td>
<td>
<script type="math/tex"><v_k,v_j></script>表示活动<script type="math/tex">a_i</script>，<script type="math/tex">e(i)=ve(k)</script>
</td>
</tr>
<tr>
<td>活动<script type="math/tex">a_i</script>的最迟发生时间<script type="math/tex">l(i)</script>
</td>
<td>
<script type="math/tex"><v_k,v_j></script>表示活动<script type="math/tex">a_i</script>，<script type="math/tex">l(i)=vl(j)-Weight(v_k,v_j)</script>
</td>
</tr>
<tr>
<td>活动<script type="math/tex">a_i</script>的最迟发生时间<script type="math/tex">l(i)</script>和最早发生时间<script type="math/tex">e(i)</script>的差额<script type="math/tex">d(i)</script>
</td>
<td>
<script type="math/tex">d(i)=l(i)-e(i)</script>
</td>
</tr>
<tr>
<td></td>
<td>
<script type="math/tex; mode=display">\begin{array}{l} a_i&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8 \\ \hline V_k&V_1&V_1&V_2&V_2&V_3&V_3&V_4&V_5 \\ V_j&V_2&V_3&V_4&V_5&V_4&V_6&V_6&V_6 \\ \hline ve(k)&0&0&3&3&2&2&6&6 \\e(i)=ve(k)&0&0&3&3&2&2&6&6 \\ \hline vl(j)&4&2&6&7&6&8&8&8 \\ Weight(i)&3&2&2&3&4&3&2&1\\ l(i)=vl(j)-Weight(i)&1&0&4&4&2&5&6&7 \\ \hline d(i)=l(i)-e(i)&1&\underline0&1&1&\underline0&3&\underline0&1\end{array}</script>
</td>
</tr>
<tr>
<td>关键活动</td>
<td>若一个活动的时间余量<script type="math/tex">d(i)=l(i)-e(i)=0</script>，说明该活动必须如期完成，该活动为关键活动。</td>
</tr>
<tr>
<td>关键路径</td>
<td>由关键活动组成的路径，如图中的：<script type="math/tex">a_2,a_5,a_7</script><br />★<strong>缩短关键活动时间可以加快整个工程，但缩短到一定大小时关键路径会发生改变。</strong><br />只提高一条关键路径上的关键活动并不能缩短整个工期，只有同时加快包含在<strong>所有关键路径</strong>上的<strong>关键活动</strong>才能达到缩短关键工期的目的。<br /><br />如<script type="math/tex">bdcg,bdeh,bfh</script>，加快<script type="math/tex">d,f</script>（注意：单个<script type="math/tex">d</script>或者<script type="math/tex">f</script>不包含在所有的关键路径中）可以缩短工期。</td>
</tr>
</tbody>
</table></div>
<h3 id="_22">知识点（顶点与边）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2009统考真题】下列关于无向连通图特性的叙述中，正确的是【I】<br /><br />&gt; 【<strong>I. 所有顶点的度之和为偶</strong>数】<br />&gt; II. ✘边数大于顶点个数-1（无向连通图的生成树，边数等于顶点个数-1）<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 13.54.58.jpg" alt="截屏2020-11-30 13.54.58" style="zoom:50%;" /><br /> III. ✘至少有一个顶点的度为1（存在所有顶点的度大于1的连通图）<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 13.56.16.jpg" alt="截屏2020-11-30 13.56.16" style="zoom:50%;" /></td>
</tr>
<tr>
<td>2.【2010统考真题】若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数至少是【16】<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 14.02.34.jpg" alt="截屏2020-11-30 14.02.34" style="zoom:50%;" /><br />考虑极端情况下，其中的6个点构成完全连通图需要5+4+3+2+1=15条边，此时再加上1条边，可以保证在任何情况下都是连通的，因此答案为16条边。</td>
</tr>
<tr>
<td>3.【2011统考真题】下列有关图的叙述中，正确的是【III】<br /><br />&gt; I. ✘回路是简单路径（回路对应路径，简单回路对应简单路径）<br />&gt; II. ✘存储稀疏图，用邻接矩阵比邻接表<u>更省空间</u>✘<br />&gt; 【<strong>III. 若有向图中存在拓扑序列，该图不存在回路</strong>】</td>
</tr>
<tr>
<td>4.【2013统考真题】设子图的邻接矩阵A如下图所示，各顶点的度依次为【3，4，2，3】<br /><br /><script type="math/tex; mode=display">A = \left[\begin{array}{} 0&1&0&1 \\ 0&0&1&1 \\ 0&1&0&0 \\ 1&0&0&0 \end{array}\right]</script><br />&gt; 顶点的度=顶点的出度（行）+入度（列）<br />&gt; 1：3（第一行+第一列）<br />&gt; 2：4（第二行+第二列）<br />&gt; 3：2<br />&gt; 4：3</td>
</tr>
<tr>
<td>5.【2016年考研408第7题】若将n个顶点，e条弧的有向图采用<strong>邻接表</strong>（注意是邻接表，非邻接矩阵）存储，则拓扑排序算法的时间复杂度为【<script type="math/tex">O(n+e)</script>】。</td>
</tr>
<tr>
<td>6.【2017统考真题】已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所包含的顶点个数至少是【11】<br /><br />&gt; <script type="math/tex">16条边=32度=所有顶点的度之和</script><br />&gt; 其他顶点的度均小于3，当其他顶点的度均为2时，顶点的个数最少<br />&gt; <script type="math/tex">32=4*3+3*4+2*n</script>得到<script type="math/tex">n=4</script><br />&gt; 总顶点数为<script type="math/tex">3+4+4=11</script>
</td>
</tr>
<tr>
<td>7. 一个有28条边的<strong>非连通无向图</strong>至少有【9】个顶点。<br /><br />&gt; 7个顶点的全连通无向图有<script type="math/tex">6+5+4+3+2+1=21</script>条边。非连通无向图有<script type="math/tex">[0,20]</script>条边。<br />&gt; 8个顶点的全连通无向图有<script type="math/tex">7+6+5+4+3+2+1=28</script>条边。非连通无向图有<script type="math/tex">[0,27]</script>条边。<br />&gt; 9个顶点的全连通无向图有<script type="math/tex">8+7+6+5+4+3+2+1=36</script>条边。非连通无向图有<script type="math/tex">[0,35]</script>条边。</td>
</tr>
<tr>
<td>8. 若具有n个顶点的图是一个环，则他有【n】颗生成树。<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 14.19.21.jpg" alt="截屏2020-11-30 14.19.21" style="zoom:50%;" /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 14.20.29.jpg" alt="截屏2020-11-30 14.20.29" style="zoom:50%;" /><br />&gt; 3个顶点的环图，有3个生成树。<br />&gt; 4个顶点的环图，有4个生成树。<br />&hellip;</td>
</tr>
<tr>
<td>9. 若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有【n-1】颗树。<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 14.22.41.jpg" alt="截屏2020-11-30 14.22.41" style="zoom:50%;" /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 14.24.06.jpg" alt="截屏2020-11-30 14.24.06" style="zoom:50%;" /><br />&gt; 添加一个结点和t条边（对应t颗树），使得森林变成一颗树<br />&gt; 根据树中结点和边的关系：<script type="math/tex">结点数-1=边数</script><br />&gt; <script type="math/tex">n+1-1=t+e</script>得到<script type="math/tex">t=n-e</script>
</td>
</tr>
<tr>
<td>10. 一个有n个顶点和n条边的无向图一定是【有环的】<br /><br />&gt; 一个无环的无向图：<script type="math/tex">顶点数-1=边数</script>
</td>
</tr>
<tr>
<td>11. 若从<strong>无向图</strong>的任意顶点出发进行一次<strong>深度优先搜索</strong>即可访问所有顶点，则该图一定是【连通的】。</td>
</tr>
</tbody>
</table></div>
<h3 id="_23">知识点（广度、深度优先搜索）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2013统考真题】若对于如下无向图进行遍历，则下列选项中，<u>不是</u><strong>广度优先遍历</strong>序列的是【D】。</td>
</tr>
<tr>
<td>2.【2016统考真题】下列选项中，<u>不是</u>下图<strong>深度优先搜索</strong>的序列的是【D】。</td>
</tr>
<tr>
<td>一般4个选项中3个是正确的，有1个是另一种搜索。（建议从D选项开始看）</td>
</tr>
<tr>
<td>3.【2015统考真题】设有向图<script type="math/tex">G=(V,E)</script>，顶点集<script type="math/tex">V=\{V_0,V_1,V_2,V_3\}</script>，边集<script type="math/tex">E=\{<v_0,v_1>,<v_0,v_2>,<v_0,v_3>,<v_1,v_3>\}</script>。若从定带你<script type="math/tex">V_0</script>开始对图进行深度优先搜索，则可能得到的不同遍历序列个数是【5】<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 15.01.38.jpg" alt="截屏2020-11-30 15.01.38" style="zoom:50%;" /><br />注意：遍历是要访问所有结点的！！！<br />&gt; <script type="math/tex">\{V_0,V_1,V_3,V_2\}</script>（注意：没有<script type="math/tex">\{V_0,V_1,V_2,V_3\}</script>，根据深度优先遍历的过程）<br />&gt; <script type="math/tex">\{V_0,V_2,V_1,V_3\}</script><br />&gt; <script type="math/tex">\{V_0,V_2,V_3,V_1\}</script><br />&gt; <script type="math/tex">\{V_0,V_3,V_1,V_2\}</script><br />&gt; <script type="math/tex">\{V_0,V_3,V_2,V_1\}</script>
</td>
</tr>
</tbody>
</table></div>
<h3 id="primdruskal">知识点（最小生成树，Prim算法和Druskal算法）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2012统考真题】下列关于最小生成树的叙述中，正确的是【只有I】<br /><br />&gt; 【<strong>I. 最小生成树的代价唯一。</strong>】<br />（当有多条边权值相等时，最小生成树的树形可能不相同，但是代价唯一）<br />&gt; ✘ II. 所有权值最小的边<u>一定会出现</u>在<u>所有</u>的最小生成树中。✘<br />（当权值最小的边有<strong>多条</strong>，并且构成<strong>环</strong>时，有权值最小的边不出现在某棵最小生成树中的情况）<br />&gt; ✘ III. 使用Prim算法从不同顶点开始得到的最小生成树<u>一定相同</u>。✘<br />（设N的顶点构成环，N-1条边的权值相等，则从不同顶点开始Prim算法会得到N-1颗不同的最小生成树）<br />&gt; ✘ IV. 使用Prim算法和Kruskal算法得到的最小生成树总<u>不相同</u>。✘<br />（当最小生成树唯一时（即各条边的权值均不相同），两种算法得到的最小生成树相同）<br />本题要注意有多条边<strong>权值相等</strong>的情况。</td>
</tr>
<tr>
<td>2.【2015统考真题】下面的带权图的最小生成树，可能是Kruskal算法第2次选中，但不是Prim算法（从V4开始）第2次选中的边是【C】<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-12-01 00.50.58.jpg" alt="截屏2020-12-01 00.50.58" style="zoom:33%;" /><br /><br />&gt; A. <script type="math/tex">(V_1,V_3)</script><br />&gt; B. <script type="math/tex">(V_1,V_4)</script><br />&gt; C. <script type="math/tex">(V_2,V_3)</script><br />&gt; D. <script type="math/tex">(V_3,V_4)</script>
</td>
</tr>
</tbody>
</table></div>
<h3 id="dijkstra">知识点（最短路径，Dijkstra算法）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2012统考真题】【2016统考真题】Dijkstra算法</td>
</tr>
</tbody>
</table></div>
<h3 id="_24">知识点（有向无环图）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2019统考真题】用有向无环图描述表达式<script type="math/tex">(x+y)((x+y)/x)</script>，需要的顶点个数至少是【5】<br /><br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-12-01 00.59.00.jpg" alt="截屏2020-12-01 00.59.00" style="zoom:33%;" /></td>
</tr>
</tbody>
</table></div>
<h3 id="_25">知识点（拓扑排序）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2010统考真题】对下图进行拓扑排序，可得不同拓扑排序序列的个数是【3】<br /><br /> <img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 23.02.39.jpg" alt="截屏2020-11-30 23.02.39" style="zoom:30%;" /><br />一共三种拓扑排序序列：<br />&gt; <span style="overflow-x: auto; max-width:100%; display:inline;"><code>a, b, c, e, d</code></span><br />&gt; <span style="overflow-x: auto; max-width:100%; display:inline;"><code>a, b, e, c, d</code></span><br />&gt; <span style="overflow-x: auto; max-width:100%; display:inline;"><code>a, e, b, c, d</code></span></td>
</tr>
<tr>
<td>2.【2012统考真题】若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为0，则关于该拓扑排序的结论是<br />【存在，可能不唯一】<br />&gt; 分析：主对角线以下的元素均为0，则图一定是一个无环有向图，则一定存在拓扑序列，但不一定唯一。<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-12-01 00.44.20.jpg" alt="截屏2020-12-01 00.44.20" style="zoom:33%;" /><script type="math/tex; mode=display">\left[\begin{array}{} 0&1&1 \\ 0&0&0 \\ 0&0&0 \end{array}\right]</script><br /><br />若主对角线以上的元素均为1，对角线以下的元素均为0，则拓扑序列唯一。</td>
</tr>
</tbody>
</table></div>
<h3 id="_26">知识点（关键路径）</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1.【2013统考真题】下列AOE网中，加快其进度就可以缩短工程工期的是【C】<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-30 23.45.15.jpg" alt="截屏2020-11-30 23.45.15" style="zoom:33%;" /><br /><br />&gt; A. c和e<br />&gt; B. d和c<br />&gt; 【<strong>C. f和d</strong>】<br />&gt; D. f和h<br /><br /><script type="math/tex; mode=display">\begin{array}{} V_k&V_1&V_2&V_3&V_4&V_5&V_6\\ \hline ve(k)&0&12&8&21&18&27 \\ vl(k)&0&12&8&21&18&27 \end{array}</script><br /><br /><script type="math/tex; mode=display">\begin{array}{l} n&a&b&c&d&e&f&g&h \\ \hline V_k&1&1&2&3&2&3&4&5 \\ V_j&2&3&4&2&5&5&6&6 \\ \hline ve(k)&0&0&12&8&12&8&21&8 \\e(i)=ve(k)&0&0&12&8&12&8&21&8 \\ \hline vl(j)&12&8&21&12&18&18&27&27 \\ Weight(i)&3&8&9&4&6&10&6&9\\ l(i)=vl(j)-Weight(i)&9&0&12&8&12&8&21&18 \\ \hline d(i)=l(i)-e(i)&9&\underline0&\underline0&\underline0&\underline0&\underline0&\underline0&\underline0\end{array}</script><br /><br />得到关键结点：<script type="math/tex">b,c,d,e,f,g,h</script><br />关键路径：<script type="math/tex">bfh,bdeh,bdcg</script><br /><br />加快<script type="math/tex">d,f</script>（注意：单个<script type="math/tex">d</script>或者<script type="math/tex">f</script>不包含在所有的关键路径中）可以缩短工期。</td>
</tr>
<tr>
<td>2.【2019统考真题】下图所示AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是【12和14】<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-12-01 00.38.45.jpg" alt="截屏2020-12-01 00.38.45" style="zoom: 33%;" /><br /><script type="math/tex; mode=display">\begin{array}{} V_k&V_1&V_2&V_3&V_4&V_5&V_6\\ \hline ve(k)&0&12&8&19&18&27 \\ vl(k)&0&12&8&21&18&27 \end{array}</script><br /><br /><script type="math/tex; mode=display">\begin{array}{l} n&a&b&c&d&e&f&g&h \\ \hline V_k&&&&2&&&& \\ V_j&&&&4&&&& \\ \hline ve(k)&&&&12&&&& \\e(i)=ve(k)&&&&12&&&& \\ \hline vl(j)&&&&21&&&& \\ Weight(i)&&&&7&&&&\\ l(i)=vl(j)-Weight(i)&&&&14&&&& \end{array}</script><br /><br />最早开始时间：<script type="math/tex">e(i)=12</script><br />最迟开始时间：<script type="math/tex">l(i)=14</script>
</td>
</tr>
</tbody>
</table></div>
<h2 id="_27">第七章 查找</h2>
<h3 id="1_18">1、顺序查找和折半查找</h3>
<h4 id="1_19">1）顺序查找</h4>
<h4 id="2_16">2）折半查找</h4>
<p>
<script type="math/tex; mode=display">
\{1,2,3,4,5,6,7,8,9,10\}
</script>
</p>
<p>1-10，10个数，构建折半查找树：</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>折半向上取整</th>
<th>折半向下取整</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<script type="math/tex">(1+10)/2=5.5\to6</script>
</td>
<td>
<script type="math/tex">(1+10)/2=5.5\to5</script>
</td>
</tr>
<tr>
<td>
<script type="math/tex">(1+5)/2=3\to3</script><br /><script type="math/tex">(7+10)/2=8.5\to9</script>
</td>
<td>
<script type="math/tex">(1+4)/2=2.5\to2</script><br /><script type="math/tex">(6+10)/2=8\to8</script>
</td>
</tr>
<tr>
<td>
<script type="math/tex">(1+2)/2=1.5\to2</script>，<script type="math/tex">(4+5)/2=4.5\to5</script><br /><script type="math/tex">(7+8)/2=7.5\to8</script>
</td>
<td>
<script type="math/tex">(3+4)/2=3.5\to3</script><br /><script type="math/tex">(6+7)/2=6.5\to6</script>，<script type="math/tex">(9+10)/2=9.5\to9</script>
</td>
</tr>
<tr>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 08.57.57.jpg" alt="截屏2020-11-26" style="zoom:25%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 09.02.24.jpg" alt="截屏2020-11-26 09.02.24" style="zoom:25%;" /></td>
</tr>
</tbody>
</table></div>
<h4 id="3_14">3）分块查找</h4>
<h3 id="2bb">2、B树和B+树</h3>
<h4 id="1b">1）B树</h4>
<p>一颗<script type="math/tex">m</script>阶<script type="math/tex">B</script>树或为空树，或为满足如下特性的<script type="math/tex">m</script>叉树：</p>
<ol>
<li>
<p>树中每个结点至多有<script type="math/tex">m</script>颗子树，至多含有<script type="math/tex">m-1</script>个关键字。</p>
</li>
<li>
<p>若根结点不是终端结点，则至少含有两颗子树。</p>
</li>
<li>
<p>除根结点外的所有非叶结点至少有<script type="math/tex">\lceil m/2 \rceil</script>颗子树，即至少含有<script type="math/tex">\lceil m/2 \rceil - 1</script>个关键字（均为向上取整）。</p>
</li>
<li>
<p>所有非叶结点的结构如下：</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>n</th>
<th>
<script type="math/tex">P_0</script>
</th>
<th>
<script type="math/tex">K_1</script>
</th>
<th>
<script type="math/tex">P_1</script>
</th>
<th>
<script type="math/tex">K_2</script>
</th>
<th>
<script type="math/tex">P_2</script>
</th>
<th>&hellip;</th>
<th>
<script type="math/tex">K_n</script>
</th>
<th>
<script type="math/tex">P_n</script>
</th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td></td>
<td>关键字</td>
<td></td>
<td>关键字</td>
<td></td>
<td></td>
<td>关键字</td>
<td></td>
</tr>
</tbody>
</table></div>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>内容</th>
<th></th>
<th>特点</th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td>
<script type="math/tex">K_1,...,K_n</script>指向子树根结点指针</td>
<td>
<script type="math/tex">K_1 \lt k_2 \lt ... \lt K_n</script>
</td>
</tr>
<tr>
<td>
<script type="math/tex">P_0</script>
</td>
<td>
<script type="math/tex">P_1,....,P_n</script>指向子树根结点指针</td>
<td>
<script type="math/tex">P_{i-1}所有结点的关键字\lt K_i \lt P_{i-1}所有结点的关键字</script>
</td>
</tr>
</tbody>
</table></div>
</li>
<li>
<p>所有叶结点都出现在同一层次上，且不带信息（这些结点的指针为空）。</p>
</li>
</ol>
<p>
<script type="math/tex">B</script>树是所有结点的平衡因子均等于<script type="math/tex">0</script>的多路平衡查找树。</p>
<h4 id="2b">2）B+树</h4>
<p>
<script type="math/tex">B+</script>树是应数据库所需而出现的一种<script type="math/tex">B</script>树的变种。</p>
<p>一颗<script type="math/tex">m</script>阶<script type="math/tex">B+</script>树满足如下特性：</p>
<ol>
<li>每个分支结点最多含有<script type="math/tex">m</script>颗子树（孩子结点）。</li>
<li>非叶根结点至少含有<script type="math/tex">2</script>颗子树，其他每个分支结点至少有<script type="math/tex">\lceil m/2 \rceil</script>颗子树。</li>
<li>结点的子树个数与关键字个数相等。</li>
<li>所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点桉大小顺序相互链接起来。</li>
<li>所有分支结点（可以视为索引的索引）中仅包含他的各个子结点（即下一级的索引快）中关键字的最大值及指向其子结点的指针。</li>
</ol>
<h4 id="bb">B树和B+树的区别</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>B树</th>
<th>B+树</th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6544.jpg" alt="IMG_6544" style="zoom:50%;" /></td>
<td><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6545.jpg" alt="IMG_6545" style="zoom:50%;" /></td>
</tr>
<tr>
<td>n关键字的结点</td>
<td>有<script type="math/tex">n+1</script>颗子树</td>
<td>有<script type="math/tex">n</script>颗子树</td>
</tr>
<tr>
<td>除根结点外的非终端结点关键字个数</td>
<td>
<script type="math/tex">\lceil m/2 \rceil -1 \le n \le m - 1</script>
</td>
<td>
<script type="math/tex">\lceil m/2 \rceil \le n \le m</script>
</td>
</tr>
<tr>
<td>根结点关键字个数</td>
<td>
<script type="math/tex">1 \le n \le m - 1</script>
</td>
<td>
<script type="math/tex">1 \le n \le m</script>
</td>
</tr>
<tr>
<td>叶结点</td>
<td>关键字与非叶结点不重复</td>
<td>包含了全部关键字</td>
</tr>
<tr>
<td>非叶结点</td>
<td>关键字与叶结点不重复</td>
<td>仅起索引作用</td>
</tr>
</tbody>
</table></div>
<h3 id="3_15">3、散列表</h3>
<h4 id="1_20">1）散列函数</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th></th>
<th>散列函数</th>
<th>特点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1. 直接定址法​</td>
<td>
<script type="math/tex">H(key) = key</script><br />或<script type="math/tex">H(key) = a * key + b</script>
</td>
<td>适合关键字分布基本连续的情况。<br />若关键字分布不连续，空位较多，则会造成存储空间的浪费。</td>
</tr>
<tr>
<td>2. 除留余数法​</td>
<td>
<script type="math/tex">H(key) = key\ \%\ p</script>
</td>
<td>最简单最常用的方法，除留余数法的关键是选好<script type="math/tex">p</script>。<br />使得每个关键字通过该函数转换后等概率的映射到散列空间上的任一地址，<br />从而尽可能减少冲突的可能性。</td>
</tr>
<tr>
<td>3. 数字分析法​</td>
<td>选取数码分布较为均匀的若干位作为散列地址。</td>
<td>适用于已知的关键字集合。</td>
</tr>
<tr>
<td>4. 平方取中法​</td>
<td>取关键字的平方的中间几位作为散列地址。</td>
<td>这种方法得到的散列地址与关键字的每位都有关系，<br />因此得到的散列地址比较均匀，<br />适用于关键字的每位取值都不够均匀或小于散列地址所需的位数。</td>
</tr>
</tbody>
</table></div>
<h4 id="2_17">2）处理冲突方法</h4>
<h5 id="1_21">1. 开放定址法</h5>
<p>
<script type="math/tex; mode=display">
H_i = (H(key) + d_i)\ \%\ m
</script>
</p>
<ol>
<li>
<script type="math/tex">H(key)</script>为散列函数</li>
<li>
<script type="math/tex">m</script>为散列表表长</li>
<li>
<script type="math/tex">d_i</script>为增量序列</li>
</ol>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>增量序列取法</th>
<th>增量序列</th>
<th>优点</th>
<th>缺点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1. 线性探测法</td>
<td>
<script type="math/tex">d_i = 0,1,2,...,m-1</script>
</td>
<td></td>
<td>可能造成“<strong>堆积</strong>”现象</td>
</tr>
<tr>
<td>2. 平方探测法</td>
<td>
<script type="math/tex">d_i = 0^2,1^2,-1^2,...,k^2,-k^2(k\le m/2)</script>
</td>
<td>避免“堆积”现象</td>
<td>不能探测散列表上所有单元<br />但至少能探测一半单元</td>
</tr>
<tr>
<td>3. 再（双）散列法</td>
<td>
<script type="math/tex">d_i = Hash_2(key)</script><br /><script type="math/tex">H_i = (H(key)+i*Hash_2(key))\ \%\ m</script>
</td>
<td></td>
<td></td>
</tr>
<tr>
<td>4. 伪随机序列法</td>
<td>
<script type="math/tex">d_i=伪随机序列</script>
</td>
<td></td>
<td></td>
</tr>
</tbody>
</table></div>
<blockquote class="content-quote">
<p><strong>“堆积”现象</strong>：存储效率，散列函数，装填因子都不会有影响，而<strong>平均查找长度</strong>会因为堆积现象而增大。</p>
</blockquote>
<h5 id="2_18">2. 链表法</h5>
<p>利用链表把冲突的地址保存起来。</p>
<p>优点：<strong>处理冲突时不会产生堆积现象。</strong></p>
<h4 id="3_16">3）散列查找</h4>
<p>影响散列表的查找效率：</p>
<ol>
<li>散列函数</li>
<li>处理冲突的方法</li>
<li>装填因子（装填因子小，查找效率高）</li>
</ol>
<h5 id="_28">装填因子：定义一个表的装满程度</h5>
<p>
<script type="math/tex; mode=display">
\alpha = \cfrac{表中记录数n}{散列表表长m}
</script>
</p>
<p>散列表的平均查找长度依赖于散列表的装填因子<script type="math/tex">\alpha</script>，而不直接依赖于<script type="math/tex">n</script>或<script type="math/tex">m</script>.</p>
<h3 id="_29">知识点</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>5. 只能在顺序存储结构上进行的查找方法是【B. 折半查找法】<br /><br />&gt; A. 顺序查找法（可以采用链式存储结构）<br />&gt; ✔︎【<strong>B. 折半查找法</strong>】（只能使用顺序存储结构）<br />&gt; C. 树形查找法<br />&gt; D. 散列查找法（链地址解决冲突法，采用顺序存储结构和链式存储结构）</td>
</tr>
<tr>
<td>4.【2011年统考真题】为提高散列表的查找效率，可以采取的正确措施有【II，III】<br /><br />&gt; I. 增大装填因子（应该为减少装填因子）<br />&gt; II. ✔︎【<strong>设计冲突少的散列函数</strong>】<br />&gt; III. ✔︎【<strong>处理冲突时避免产生堆积现象</strong>】<br /><br />&gt; 散列表的查找效率取决于：1. 散列函数，2. 处理冲突的方法，3. 装填因子（装填因子小，查找效率高）<br />&gt; 用链地址法处理冲突时不存在堆积现象。<br />&gt; 用线性探测法处理冲突容易产生堆积现象。</td>
</tr>
<tr>
<td>1.【2013年考研408第10题】高度为2的5阶B树，所含关键字的个数最少是【5】<br /><br />&gt; 5阶B树，根结点关键字个数<script type="math/tex">1\le n\le 5-1</script>，即<script type="math/tex">[1,4]</script><br />&gt; 5阶B树，除根结点外的非终端结点的关键字个数<script type="math/tex">\lceil5/2\rceil-1\le n\le 5-1</script>，即<script type="math/tex">[2,4]</script><br />&gt; 试题解答里面说：5阶B树只有在根结点到达了5个关键字的时候才能分裂成高度为2的5阶B树。<br /><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/截屏2020-11-26 20.37.52-6394552.jpg" alt="截屏2020-11-26 20.37.52" style="zoom:50%;" /><br />&gt; 总计：<script type="math/tex">1+2*2=5</script>，至少含有5个关键字。</td>
</tr>
<tr>
<td>7.【2014年考研408第8题】用哈希方法处理冲突时可能会产生堆积现象，会首堆积现象直接影响的是【D. 平均查找长度】<br /><br />&gt; A. 存储效率<br />&gt; B. 散列函数<br />&gt; C. 装填因子<br />&gt; ✔︎【<strong>D. 平均查找长度</strong>】</td>
</tr>
<tr>
<td>2.【2018年考研408真题】高度为5的3阶B树含有的关键字个数至少是【31】<br /><br />&gt; 3阶B树，根结点关键字个数<script type="math/tex">1\le n\le 3-1</script>，即<script type="math/tex">[1,2]</script><br />&gt; 3阶B树，除根结点外的非终端结点的关键字个数<script type="math/tex">\lceil3/2\rceil-1\le n\le 3-1</script>，即<script type="math/tex">[1,2]</script><br /><br />&gt; 高度5，第一层（根）：至少含有1个根结点，<script type="math/tex">1*1</script>个关键字，2个子树。<br />&gt; 高度4，第二层：至少含有2个结点，<script type="math/tex">2*1</script>个关键字，<script type="math/tex">2*2=4</script>个子树。<br />&gt; 高度3，第三层：至少含有4个结点，<script type="math/tex">4*1</script>个关键字，<script type="math/tex">4*2=8</script>个子树。<br />&gt; 高度2，第四层：至少含有8个结点，<script type="math/tex">8*1</script>个关键字，<script type="math/tex">8*2=16</script>个子树。<br />&gt; 高度1，第五层：至少含有16个结点，<script type="math/tex">16*1</script>个关键字，<script type="math/tex">16*2=32</script>个子树。<br />&gt; 总计：<script type="math/tex">1+2+2^2+2^3+2^4 = 31</script>，至少含有31个关键字。<br /><br />&gt; 总结：此高度为5的3阶B树，取最少关键字时，与高度为5的满二叉树相同。</td>
</tr>
<tr>
<td>3.【2018年考研408第9题】现有初始长度为7，初始化为空的散列表HT，散列函数为<script type="math/tex">H(k)=k\%7</script>，用<strong>线性探测</strong>再散列法解决冲突。将关键字22，43，15依次插入到HT后，查找成功的平均查找长度为【2】<br /><br />&gt; 22 43 15 <strong> </strong> <strong> </strong><br />&gt; <script type="math/tex">(1+2+3)/2=3</script><br />&gt; 注意本题是<strong>线性探测法</strong></td>
</tr>
<tr>
<td>6. 在开放定址法中散列到同一个地址而引起的“堆积”现象是由于【同义词之间或非同义词之间发生冲突】。</td>
</tr>
<tr>
<td>8.【2018年统考真题】现有长度为11且初始为空的散列表HT，散列函数是<script type="math/tex">H(key)=key\%7</script>，用<strong>线性探测法</strong>解决冲突。将关键序列<script type="math/tex">87,40,30,6,11,22,98,20</script>依次插入HT后，HT查找失败的平均长度为【6】<br /><br />&gt; 计算哈希值<script type="math/tex">98,22,30,87,11,40,6,20</script>（其实本题不用计算出哈希值，8个序号，一定占用了哈希表的0～7号地址）<br />&gt; 对于线性探测法，查找时，对于计算出哈希值为0的查找数，需要比较0～8号地址才能确定其是否在哈希表中，即9次。<br />&gt; 对于计算出哈希值为1的查找数，需要比较1～8号，8次。<br />&gt; &hellip;<br />&gt; 对于计算出哈希值为6的查找数，需要比较6～8号，3次。<br />&gt; 总计：<script type="math/tex">(9+8+7+6+5+4+3)/7=42/7=6</script>
</td>
</tr>
<tr>
<td></td>
</tr>
</tbody>
</table></div>
<h2 id="_30">第八章 排序</h2>
<ol>
<li>内部排序<ol>
<li>插入排序<ol>
<li>直接插入排序</li>
<li>折半插入排序</li>
<li>希尔排序<strong>（内部排序使用直接插入排序）</strong></li>
</ol>
</li>
<li>交换排序<ol>
<li>冒泡排序</li>
<li>快速排序</li>
</ol>
</li>
<li>选择排序<ol>
<li>简单选择排序</li>
<li>堆排序</li>
</ol>
</li>
<li>归并排序</li>
<li>基数排序</li>
</ol>
</li>
<li>外部排序<ol>
<li>多路归并排序</li>
</ol>
</li>
</ol>
<h4 id="1_22">1）类别</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>类别</th>
<th>描述</th>
</tr>
</thead>
<tbody>
<tr>
<td>比较类排序</td>
<td>通过比较来决定元素间的相对次序，由于其时间复杂度不能突破<script type="math/tex">O(n\log n)</script>，因此也称为非线性时间比较类排序。</td>
</tr>
<tr>
<td>非比较类排序</td>
<td>不通过比较来决定元素间的相对次序，它<strong>可以突破基于比较排序的时间下界</strong>，以线性时间运行，因此也称为线性时间非比较类排序。</td>
</tr>
</tbody>
</table></div>
<h4 id="2_19">2）相关概念</h4>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>概念</th>
<th>描述</th>
</tr>
</thead>
<tbody>
<tr>
<td><u>稳定</u></td>
<td>如果a原本在b前面，而a=b，排序之后a仍然在b的前面。</td>
</tr>
<tr>
<td>不稳定</td>
<td>如果a原本在b的前面，而a=b，排序之后 a <strong>可能</strong>会出现在 b 的后面。</td>
</tr>
<tr>
<td>时间复杂度</td>
<td>对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。</td>
</tr>
<tr>
<td>空间复杂度</td>
<td>是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。</td>
</tr>
</tbody>
</table></div>
<h3 id="1_23">1、插入排序</h3>
<h4 id="1_24">1）直接插入排序</h4>
<p>黄色表示已排序部分，蓝色表示未排序部分，红色表示当前正在处理的key</p>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/插入排序.mov"></video>

<h4 id="2_20">2）折半插入排序</h4>
<h4 id="3shell">3）Shell希尔排序</h4>
<p>（2014年考研408第10题）</p>
<p>希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/IMG_6548.jpg" alt="IMG_6548" style="zoom:50%;" /></p>
<h3 id="2_21">2、交换排序</h3>
<h4 id="1_25">1）冒泡排序</h4>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/冒泡排序.mov"></video>

<h4 id="2_22">2）快速排序</h4>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/快速排序.mov"></video>

<h3 id="3_17">3、选择排序</h3>
<h4 id="1_26">1）简单选择排序</h4>
<p>黄色表示已排序部分，蓝色表示未排序部分，红色表示从未排序中选择的最小值。</p>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/选择排序.mov"></video>

<h4 id="2_23">2）堆排序</h4>
<blockquote class="content-quote">
<p>转载自：<a href="https://www.cnblogs.com/chengxiao/p/6129630.html">图解排序算法(三)之堆排序</a></p>
</blockquote>
<p>堆排序是利用<strong>堆</strong>这种数据结构而设计的一种排序算法，堆排序是一种<strong>选择排序，</strong>它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。</p>
<p><strong>堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：</strong></p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161217182750011-675658660.jpg" alt="1024555-20161217182750011-675658660" style="zoom: 33%;" /></p>
<p>同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161217182857323-2092264199.jpg" alt="1024555-20161217182857323-2092264199" style="zoom: 20%;" /></p>
<p>该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：</p>
<p><strong>大顶堆：arr[i] &gt;= arr[2i+1] &amp;&amp; arr[i] &gt;= arr[2i+2]</strong>  </p>
<p><strong>小顶堆：arr[i] &lt;= arr[2i+1] &amp;&amp; arr[i] &lt;= arr[2i+2]</strong>  </p>
<p><strong>堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。</strong></p>
<p>步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。</p>
<p>1.假设给定无序序列结构如下</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161217192038651-934327647.jpg" alt="1024555-20161217192038651-934327647" style="zoom: 33%;" /></p>
<p>2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161217192209433-270379236.jpg" alt="1024555-20161217192209433-270379236" style="zoom: 33%;" /></p>
<p>3.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161217192854636-1823585260.jpg" alt="1024555-20161217192854636-1823585260" style="zoom: 33%;" /></p>
<p>这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161217193347886-1142194411.jpg" alt="1024555-20161217193347886-1142194411" style="zoom: 33%;" /></p>
<p>此时，我们就将一个无需序列构造成了一个大顶堆。</p>
<p>步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。</p>
<p>1.将堆顶元素9和末尾元素4进行交换</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161217194207620-1455153342.jpg" alt="1024555-20161217194207620-1455153342" style="zoom: 33%;" /></p>
<p>2.重新调整结构，使其继续满足堆定义</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161218153110495-1280388728.jpg" alt="1024555-20161218153110495-1280388728" style="zoom: 33%;" /></p>
<p>3.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161218152929339-1114983222.jpg" alt="1024555-20161218152929339-1114983222" style="zoom: 33%;" /></p>
<p>后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序</p>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/1024555-20161218152348229-935654830.jpg" alt="1024555-20161218152348229-935654830" style="zoom: 33%;" /></p>
<p><strong>算法思想：</strong></p>
<ol>
<li>将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆</li>
<li>将堆顶元素与末尾元素交换，将最大元素&rdquo;沉&rdquo;到数组末端;</li>
<li>重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。</li>
</ol>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/桶排序.mov"></video>

<h3 id="4_9">4、归并排序</h3>
<p>归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。</p>
<p><strong>算法思想</strong>：</p>
<ol>
<li>把长度为n的输入序列分成两个长度为n/2的子序列；</li>
<li>对这两个子序列分别采用归并排序；</li>
<li>将两个排序好的子序列合并成一个最终的排序序列。</li>
</ol>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/归并排序.mov"></video>

<h3 id="5_2">5、桶排序</h3>
<p>将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。</p>
<p><strong>算法思想</strong>：</p>
<ol>
<li>设置一个定量的数组当作空桶子。</li>
<li>寻访序列，并且把项目一个一个放到对应的桶子去。</li>
<li>对每个不是空的桶子进行排序。</li>
<li>从不是空的桶子里把项目再放回原来的序列中。</li>
</ol>
<p><img class="pure-img" src="https://zromyk.gitee.io/myblog-figurebed/post/计算机考研-算法与数据结构.assets/EFVBVn-20201124115729853.gif" alt="img" style="zoom:200%;" /></p>
<h3 id="6">6、计数排序</h3>
<ol>
<li>计数排序统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。</li>
<li>计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，<strong>一般是用来排序 0 到 100 之间的数字的最好的算法</strong>，但是它不适合按字母顺序排序人名。</li>
<li>计数排序不是比较排序，<strong>排序的速度快于任何比较排序算法</strong>。</li>
</ol>
<p><strong>算法思想</strong>：</p>
<ol>
<li>找出待排序的数组中最大和最小的元素；</li>
<li>统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；</li>
<li>对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；</li>
<li>向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；</li>
</ol>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/计数排序.mov"></video>

<h3 id="7">7、基数排序</h3>
<p>一种多关键字的排序算法，可用桶排序实现。</p>
<video style="border: 1px solid rgba(0, 0, 0, 1);" controls="controls" width="100%" height="100%" src="/post/计算机考研-算法与数据结构.assets/基数排序.mov"></video>

<h3 id="8">8、各种内部排序算法的比较与应用</h3>
<p>特点：第<strong><script type="math/tex">i</script>趟完成</strong>时，会有<strong><script type="math/tex">i</script>个以上</strong>的元素出现在它最终要出现的位置，即他的左边都比他小，他的右边都比他大。</p>
<p>下列排序算法具有该特点：</p>
<ol>
<li>选择排序<ol>
<li><strong>简单选择排序</strong></li>
<li><strong>堆排序</strong></li>
</ol>
</li>
<li>交换排序<ol>
<li><strong>冒泡排序</strong></li>
<li><strong>快速排序</strong>（每趟排序会划分2个区域，区域中轴为最终确定数）</li>
</ol>
</li>
</ol>
<p><strong>比较型算法的时间复杂度最优也只能到达<script type="math/tex">O(n\log_2n)</script></strong></p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>排序算法</th>
<th>平均</th>
<th>最坏</th>
<th>最好</th>
<th>空间复杂度</th>
<th>稳定性</th>
<th>特点</th>
</tr>
</thead>
<tbody>
<tr>
<td>直接插入排序</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n)</script>
</td>
<td>
<script type="math/tex">O(1)</script>
</td>
<td><strong>稳定</strong></td>
<td></td>
</tr>
<tr>
<td>折半插入排序</td>
<td>同上</td>
<td>同上</td>
<td>同上</td>
<td>同上</td>
<td><strong>稳定</strong></td>
<td></td>
</tr>
<tr>
<td>希尔排序</td>
<td>特别<script type="math/tex">O(n^{1.3})</script>
</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n)</script>
</td>
<td>
<script type="math/tex">O(1)</script>
</td>
<td>不稳定</td>
<td></td>
</tr>
<tr>
<td>简单选择排序</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(1)</script>
</td>
<td>不稳定</td>
<td>具有</td>
</tr>
<tr>
<td>堆排序</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(1)</script>
</td>
<td>不稳定</td>
<td>具有</td>
</tr>
<tr>
<td>冒泡排序</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n)</script>
</td>
<td>
<script type="math/tex">O(1)</script>
</td>
<td><strong>稳定</strong></td>
<td>具有</td>
</tr>
<tr>
<td>快速排序</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>不稳定</td>
<td>具有</td>
</tr>
<tr>
<td>归并排序</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(n\log_2n)</script>
</td>
<td>
<script type="math/tex">O(n)</script>
</td>
<td><strong>稳定</strong></td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>计数排序</td>
<td>
<script type="math/tex">O(n+k)</script>
</td>
<td>
<script type="math/tex">O(n+k)</script>
</td>
<td>
<script type="math/tex">O(n+k)</script>
</td>
<td>
<script type="math/tex">O(n+k)</script>
</td>
<td>稳定</td>
<td></td>
</tr>
<tr>
<td>桶排序</td>
<td>
<script type="math/tex">O(n+k)</script>
</td>
<td>
<script type="math/tex">O(n^2)</script>
</td>
<td>
<script type="math/tex">O(n)</script>
</td>
<td>
<script type="math/tex">O(n+k)</script>
</td>
<td>稳定</td>
<td></td>
</tr>
<tr>
<td>基数排序</td>
<td>
<script type="math/tex">O(n*k)</script>
</td>
<td>
<script type="math/tex">O(n*k)</script>
</td>
<td>
<script type="math/tex">O(n*k)</script>
</td>
<td>
<script type="math/tex">O(n+k)</script>
</td>
<td>稳定</td>
<td></td>
</tr>
</tbody>
</table></div>
<h3 id="9">9、外部排序</h3>
<h4 id="1_27">1）多路归并与败者树</h4>
<h4 id="2-">2）置换-选择排序</h4>
<h4 id="3_18">3）最佳归并树</h4>
<h3 id="_31">知识点</h3>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>8.【2010年统考真题】采用递归方式对顺序表进行快速排序，对于递归次数叙述正确的是【D】<br /><br />&gt; A. 递归次数与初始数据的排列无关（错误，只<strong>与初始数据的排列有关</strong>）<br />&gt; B. 每次划分后，先处理较长的分区可以减少递归次数<br />&gt; C. 每次划分后，先处理较短的分区可以减少递归次数<br />&gt; 【<strong>D. 递归次数与每次划分后得到的分区的处理顺序无关</strong>】</td>
</tr>
<tr>
<td>2.【2012年统考真题】对同一待排序序列分别进行<strong>折半插入排序</strong>和<strong>直接插入排序</strong>，两者之间可能的不同之处是【D】<br /><br />&gt; A. 排序的总趟数（相同，都是n-1趟）<br />&gt; B. 元素的移动次数（相同，都取决于初始序列）<br />&gt; C. 使用辅助空间的数量（相同，均为<script type="math/tex">O(1)</script>）<br />&gt; 【<strong>D. 元素之间的比较次数</strong>】<br /><br />折半插入排序的比较次数与序列初始状态无关，<script type="math/tex">O(n\log_2n)</script><br />直接插入排序的比较次数与序列初始状态有关，<script type="math/tex">O(n)\sim O(n^2)</script>
</td>
</tr>
<tr>
<td>7.【2014年统考真题】不可能是快速排序第二趟的排序结果的是【C】<br /><br />正确排序：<script type="math/tex">2,3,4,5,6,7,9</script><br /><br />&gt; A. <script type="math/tex">\underline{2},\underline{3},\underline{4},\underline{5},\underline{6},\underline{7},\underline{9}</script>（&hellip;）<br />&gt; B. <script type="math/tex">\underline{2},7,5,6,4,3,\underline{9}</script>（第一趟9，第二趟2，或者，第一趟2，第二趟9）<br />&gt; C. <script type="math/tex">3,2,5,4,7,6,\underline{9}</script>（不可能）<br />&gt; D. <script type="math/tex">4,2,3,\underline{5},7,6,\underline{9}</script>（第一趟9，第二趟5）</td>
</tr>
<tr>
<td>3.【2015年统考真题】希尔排序的组内排序采用的是【直接插入排序】</td>
</tr>
<tr>
<td>1.【2016年考研408第11题】对10TB数据进行排序，应使用的方法是【归并排序】<br /><br />&gt; A. 希尔排序，B. 堆排序，C. 快速排序，【<strong>D. 归并排序</strong>】</td>
</tr>
<tr>
<td>6.【2019年统考真题】排序过程中对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是【D】<br /><br />正确排序：<script type="math/tex">\ 2,\ 5,12,16,28,32,60,72</script><br /><br />&gt; A. <script type="math/tex">\ 5,\ 2,16,12,\underline{28},60,32,\underline{72}</script>（第一趟72，第二趟28）<br />&gt; B. <script type="math/tex">\underline{\ 2},16,\ 5,28,12,60,32,\underline{72}</script>（第一趟72，第二趟2，或者，第一趟2，第二趟72）<br />&gt; C. <script type="math/tex">\underline{\ 2},12,16,\ 5,\underline{28},\underline{32},72,60</script>（第一趟2，第二趟28/32）<br />&gt; D. <script type="math/tex">\ 5,\ 2,\underline{12},28,16,\underline{32},72,60</script><br /><br />（若第一趟是12，则第二趟排序完成，12的左边和右边都有1个最终确定数，即2个确定数，然而D选项中不成立）<br />（若第一趟是32，则第二趟排序完成，32的左边和右边都有1个最终确定数，即2个确定数，然而D选项中不成立）<br /><br />故，此题D是不可能的。</td>
</tr>
<tr>
<td>4. 有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终位置上，只有下列排序算法才会有这种情况：<br />&gt; 选择排序：简单选择排序，堆排序<br />&gt; 交换排序：冒泡排序，快速排序</td>
</tr>
<tr>
<td>5. 在待排序的元素序列基本有序的前提下，效率最高的排序算法是【直接插入排序】<br /><br />&gt; A. 直接插入排序，B. 简单选择排序，C. 快速排序，D. 归并排序<br />&gt; 根据最好情况下的时间复杂度来判断。</td>
</tr>
</tbody>
</table></div>
</div>
<div id="nav">
  <div class="navigation">
  <ul class="pure-menu-list">
    <li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_1">第一章 绪论</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1">1、算法与数据结构基本概念</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#_2">例题</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_3">知识点</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_4">第二章 线性表</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#2">2、线性表的顺序表示</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#3">3、线性表的链式表示</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_1">1）单向链表</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_1">2）双向链表</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_1">3）循环链表</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#4">4）静态链表</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_5">知识点</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_6">第三章 栈和队列</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#1_2">1、栈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_3">1）顺序栈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_2">2）共享栈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_2">3）链式栈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#2_3">2、栈的应用</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_4">1）栈在括号匹配</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_4">2）栈在表达式求值</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_3">3）栈在递归</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#3_4">3、队列</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_5">1）顺序队列（不实用）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_5">2）循环顺序队列</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_5">3）队列的链式存储</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#4_1">4）双端队列</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#4_2">4、队列的应用</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_6">1）队列在层次遍历</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_6">2）队列在计算机系统</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#5">5、特殊矩阵的压缩存储</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_7">1）对称矩阵</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_7">2）三角矩阵</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_6">3）三对角矩阵</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#4_3">4）稀疏矩阵</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#1_8">（1）三元组（行，列，值）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#2_8">（2）十字链表</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_7">知识点</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_8">第四章 串</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#1_9">1、串的模式匹配</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#kmp">KMP算法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_9">知识点</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_10">第五章 树与二叉树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#0">0、二叉树的定义</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#1_10">1、二叉树的遍历</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_11">1）二叉树的遍历（前、中、后）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#onon">二叉树的遍历（递归，<script type="math/tex">O(n),O(n)</script>）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#onon_1">二叉树的遍历（迭代，<script type="math/tex">O(n),O(n)</script>）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#morrisono1">二叉树的遍历（morris，<script type="math/tex">O(n),O(1)</script>）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_9">2）三种遍历方式的关系</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_7">3）层次遍历</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#4_4">4）深度优先遍历和广度优先遍历</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#2_10">2、线索二叉树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#3_8">3、树、森林</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_12">1）表示方法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_11">2）森林与二叉树的转换</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_9">3）森林的遍历</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#4_5">4）树的应用——并查集</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#4_6">4、树与二叉树的应用</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_13">1）二叉排序树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2avl">2）平衡二叉树（AVL）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_10">3）哈夫曼树和哈夫曼编码</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#1_14">1. 哈夫曼树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#2_12">2. 前缀编码</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_11">树的性质</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_12">知识点（树的结点个数）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_13">知识点（树的遍历）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_14">知识点（二叉排序查找树）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#avl">知识点（平衡二叉树，AVL）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_15">知识点（最小带权路径树，哈夫曼）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_16">知识点（森林转化为树）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_17">第六章 图</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#1_15">1、图的表示</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#2_13">2、图的存储</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#_18">网络的邻接矩阵表示法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#3_11">3、图的遍历</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_16">1）广度优先搜索</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_14">2）深度优先搜索</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_12">3）图的连通性</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#4_7">4、图的应用</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_17">1）最小生成树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_15">2）最短路径</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_13">3）有向无环图描述表达式</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#4_8">4）拓扑排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#_19">有向无环图</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#_20">拓扑排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#_21">逆拓扑排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#5_1">5）关键路径</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#aoe">AOE网</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_22">知识点（顶点与边）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_23">知识点（广度、深度优先搜索）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#primdruskal">知识点（最小生成树，Prim算法和Druskal算法）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#dijkstra">知识点（最短路径，Dijkstra算法）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_24">知识点（有向无环图）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_25">知识点（拓扑排序）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_26">知识点（关键路径）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_27">第七章 查找</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#1_18">1、顺序查找和折半查找</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_19">1）顺序查找</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_16">2）折半查找</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_14">3）分块查找</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#2bb">2、B树和B+树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1b">1）B树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2b">2）B+树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#bb">B树和B+树的区别</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#3_15">3、散列表</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_20">1）散列函数</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_17">2）处理冲突方法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#1_21">1. 开放定址法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#2_18">2. 链表法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_16">3）散列查找</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 2.25em;" href="#_28">装填因子：定义一个表的装满程度</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_29">知识点</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 0.75em;" href="#_30">第八章 排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_22">1）类别</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_19">2）相关概念</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#1_23">1、插入排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_24">1）直接插入排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_20">2）折半插入排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3shell">3）Shell希尔排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#2_21">2、交换排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_25">1）冒泡排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_22">2）快速排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#3_17">3、选择排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_26">1）简单选择排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2_23">2）堆排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#4_9">4、归并排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#5_2">5、桶排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#6">6、计数排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#7">7、基数排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#8">8、各种内部排序算法的比较与应用</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#9">9、外部排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#1_27">1）多路归并与败者树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#2-">2）置换-选择排序</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.75em;" href="#3_18">3）最佳归并树</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" style="padding:0.1em 0em 0.1em 1.25em;" href="#_31">知识点</a>
</li>

  </ul>
</div>

</div>
 
    </div>
  </div>
  <div id="footer">
    <div class="legal pure-g">
  <div class="pure-u-1 u-sm-1-2">
    <p class="legal-license"><a href="https://beian.miit.gov.cn/#/Integrated/index">浙ICP备2020038748号</a></p>
  </div>
  <div class="pure-u-1 u-sm-1-2">
    <p class="legal-links"><a href="https://github.com/zromyk">GitHub</a></p>
    <p class="legal-copyright">Copyright © 2020 Wei Zhou. 保留所有权利。</p>
  </div>
</div>
  </div>
</body>
</html>
